Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
翻译
有一个int数组，从中找到这样的两个数字，他们之和等于指定的目标值。
函数twoSum需要返回这两个数的索引，这两个数之和等于目标，且索引1必须小于索引2。请注意你返回的答案（索引1和索引2都）不是以零位基准的。
你可以假设每个输入都会只有一个解决方案。
输入：numbers={2, 7, 11, 15}, target=9
输出：index1=1, index2=2
要点：
审题发现：
0.返回的是索引
1.“且索引1必须小于索引2”，注意判断一下谁大谁小再返回
2.“不是以零位基准的”，记得索引值加一
3.“可以假设每个输入都会只有一个解决方案”，说明不会出现没有答案的情况（如，numbers长度问题，numbers中无解，numbers中多解）
另外注意：
1.数组可能是乱序的，记得排序
2.数组可能超级长。。。注意时间复杂度
3.数组可能有负数，记得返回的索引值
我的解决方案
class Node implements Comparable<Node> {
public int index;
public int value;
public Node(int index, int value) {
this.index = index;
this.value = value;
}
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
public int[] twoSum(int[] numbers, int target) {
// 排序。。。尼玛还要手写。。。
Node[] nodes = new Node[numbers.length];
for (int i = 0; i < numbers.length ; i++) {
nodes[i] = new Node(i,numbers[i]);
}
Arrays.sort(nodes);
int[] result = {0,0};
int index1 = 0;
int index2 = numbers.length-1;
//当前后指针不相撞的时候
while (index1 < index2) {
//和小于，加大前面
if ((nodes[index1].value + nodes[index2].value) < target) {
index1++;
continue;
}
//和大于，减小后面
if ((nodes[index1].value + nodes[index2].value) > target) {
index2--;
continue;
}
//相等了。。。
result[0] = nodes[index1].index+1;
result[1] = nodes[index2].index+1;
break;
}
if (result[0] > result[1]) {
result[0] = result[1] ^ result[0];
result[1] = result[1] ^ result[0];
result[0] = result[1] ^ result[0];
}
return result;
}
