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

翻譯
有一個(gè)int數(shù)組，從中找到這樣的兩個(gè)數(shù)字，他們之和等于指定的目標(biāo)值。
函數(shù)twoSum需要返回這兩個(gè)數(shù)的索引，這兩個(gè)數(shù)之和等于目標(biāo)，且索引1必須小于索引2。請注意你返回的答案（索引1和索引2都）不是以零位基準(zhǔn)的。

你可以假設(shè)每個(gè)輸入都會只有一個(gè)解決方案。

輸入：numbers={2, 7, 11, 15}, target=9
輸出：index1=1, index2=2

要點(diǎn)：
審題發(fā)現(xiàn)：
0.返回的是索引
1.“且索引1必須小于索引2”，注意判斷一下誰大誰小再返回
2.“不是以零位基準(zhǔn)的”，記得索引值加一
3.“可以假設(shè)每個(gè)輸入都會只有一個(gè)解決方案”，說明不會出現(xiàn)沒有答案的情況（如，numbers長度問題，numbers中無解，numbers中多解）
另外注意：
1.數(shù)組可能是亂序的，記得排序
2.數(shù)組可能超級長。。。注意時(shí)間復(fù)雜度
3.數(shù)組可能有負(fù)數(shù)，記得返回的索引值

我的解決方案

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;
    //當(dāng)前后指針不相撞的時(shí)候
    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;
}

https://leetcode.com/submissions/detail/25418121/