解题思路:
1: 直接暴力遍历 复杂度O(n*n) 超时
2:先排序,再遍历 增加了空间复杂度,时间复杂度为O(N+N*log(N)+N)
public int[] twoSum(int[] numbers, int target) {
? assert (numbers == null || numbers.length < 2);
class node {//辅助类
int index;
int value;
public node(int index, int value){ this.index = index; this.value = value; };
}
int[] rs = { 0, 0 };
List
nodes = new ArrayList
(); for (int index = 0 ;index< numbers.length; ++index){ nodes.add(new node(index+1, numbers[index]));//index 从1开始 } Collections.sort(nodes, new Comparator
() {//排序 @Override public int compare(node o1, node o2) { return o1.value - o2.value; } }); int i = 0, j = nodes.size()-1; while (i
target){ j --; continue; } if(v1 + v2 == target){ rs[0] = Math.min(nodes.get(i).index, nodes.get(j).index); rs[1] = Math.max(nodes.get(i).index, nodes.get(j).index); return rs; } if(v1 + v2 < target){ i ++; continue; } } return rs; }