[LeetCode]Two Sum

[LeetCode]Two Sum

題意:求出某個數組中的兩個數值的和等於一個固定的target的該兩個數值的下標,按從小到大的順序.
解題思路:
1: 直接暴力遍歷 復雜度O(n*n) 超時
2:先排序,再遍歷 增加了空間復雜度,時間復雜度為O(N+N*log(N)+N)
3:有人建議用HashMap但是如果有重復數據就應該是不成立的,思路二的解法如下:

    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;
    }