Two sum

最簡單的一題，也是 leetcode 第一題

要求從一組數列裡，找出兩個數相加等於給的 target

然後要回傳兩個 index，題目保證會有解

第一個方法最簡單就是暴力解，複雜度 O(n^2)

不過當然不行啦，哪有這麼簡單

第二個方法是兩根指針，

一個指向頭，一個指向尾，每次判斷這兩個位置的和是不是 target

如果相加的數字大於 target 那右指針往左，反之左指針往右

這裡要注意的是這樣做需要先排序，不排序的話會不知道是左指針要往右還是右指針往左

排序後的 index 會亂掉，要做額外處理，

排序的複雜度是 O(n log n)，掃指針是 O(n)，所以複雜度是 O(n log n)

class Number {
    Integer index;
    Integer value;
    public Number(Integer index, Integer value) {
        this.index = index;
        this.value = value;
    }
    public Integer getValue() {
        return value;
    }
}

class ValueComparator implements Comparator<Number> {    
    @Override    
    public int compare(Number o1, Number o2) {    
        return o1.getValue().compareTo(o2.getValue());      
    }
 }

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[]{-1, -1};

    if (nums == null || nums.length < 2) {
        return res;
    }

    //init number array
    Number[] numbers = new Number[nums.length];
    for (int i=0; i<nums.length; i++) {
        numbers[i] = new Number(i, nums[i]);
    }
    Arrays.sort(numbers, new ValueComparator());
    int head = 0;
    int tail = numbers.length-1;
    while (head < tail) {
        if (numbers[head].value + numbers[tail].value == target) {
            res[0] = numbers[head].index;
            res[1] = numbers[tail].index;
            break;
        }
        else if (numbers[head].value + numbers[tail].value > target) {
            tail--;
        } else {
            head++;
        }
    }
    return res;     
}

第三種是用 hash map

我們可以遍歷數組，然後每次檢查 target - nums[i] 是不是在 hash map裡

如果不是，就把 nums[i] 存到 hash map，value 是 index

如果有，那表示 nums[i] 和 target - nums[i] 這兩個的 index是解

複雜度是 O(n) ，只要遍歷一次數組即可

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[]{-1, -1};

    if (nums == null || nums.length < 2) {
        return res;
    }

    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            res[0] = map.get(target - nums[i]);
            res[1] = i;
        } else {
            map.put(nums[i], i);
        }
    }
    return res;
}