LeetCode 1. Two Sum

題目：輸入一個整數陣列與目標答案，回傳陣列中哪兩個位置相加會等於目標值。

難度：Easy

Example：

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

解法：

一開始看到這問題的時後，最直覺得暴力解法就是用兩個迴圈去檢查兩值相加等於目標。

class Solution {
    public int[] twoSum(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++){
                int a = nums[i] + nums[j];
                if(a == target){
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }
}

不過因為是兩個迴圈的關係，效能似乎有點差。系統說我贏過41.3%的提交結果。

進階：

Google後發現用HashMap效能會比較好。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length ; i++) {
            int a =  nums[i];
            if(map.containsKey(target-a)){
                // 如果 target - a可以在map中找到值x，代表之前已經出現過值x， target = x + a
                // 因此回傳 x的位置與目前a的位置  
                result[0] = map.get(target-a);
                result[1] = i;
                return result;
            } else {
                // 使用map儲存目前的數字與其位置  
                map.put(a, i);
            }
        }
        return result;
    }
}

運行時間贏過85.10%的提交結果。