TwoSum之Java實現

一、題目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example：
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

二、題目理解

給定一個整型數組以及一個目標值，求數組中兩個相加等于目標值的元素的索引。此題假設給定的數組中一定有兩個元素相加等于目標值。

三、實現代碼

1、第一種實現方式
使用暴力搜索的方式，用雙層for循環遍歷數組，拿數組的每一個元素與其他元素相加之后與目標值進行對比，找出符合要求的兩個元素。
實現代碼如下：

public int[] twoSum01(int[] nums, int target) {
    int[] result = new int[2];
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                break;
            }
        }
    }
    return result;
}

2、第二種實現方式
第一種實現方式在最壞的情況下的時間復雜度為O(n2)，執行時間較長，不是一種比較好的實現方式，下面是第二種實現方法。
定義一個Map，遍歷數組，每次都用目標值減去數組當前值得到差值temp，并判斷temp是否存在于Map中，如不存在，則將數組當前值和索引存入Map中；如存在，則取出temp對應的索引值。
實現代碼如下：

public int[] twoSum02(int[] nums, int target) {
    HashMap<Integer, Integer> tempMap = new HashMap<Integer, Integer>();
    int[] resultArr = new int[2];
    for(int i = 0; i < nums.length; i++) {
        // 用target減去數組當前值
        int temp = target - nums[i];
        // 判斷HashMap中是否包含temp
        if(tempMap.get(temp) != null) {
            resultArr[0] = tempMap.get(temp);
            resultArr[1] = i;
            break;
        } else {
            tempMap.put(nums[i], i);        // 如不包含，就將當前值存入Map中
        }
    }
    return resultArr;
}