【LittleDuck_LeetCodeNote】01 - Two Sum

Question and Hints

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

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• Only one valid answer exists.

First Solution

💡 設計一個ans作為output，用兩個迴圈以排列組合的方式捉對比較，符合的就放進ans，排序後進行return。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        for(int i = 0; i < nums.length-1; i++){
            for(int j = i+1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    ans[0] = i;
                    ans[1] = j;
                    Arrays.sort(ans);
                }     
            }
        }
        return ans;
    }
}

Upgrade Solution

💡 建立一個HashMap，result用於存放index，用一個for loop同時將nums的值放進HashTable並逐一檢查，當有找到或是全部沒找到，就回傳result.

1. 每圈for loop先設定一個findValue，內容為target — nums值

2. 第一圈，nums = 2, findValue = 9–2=7, containsKey(findValue) = false, map.put(0,2);

3. 第二圈，nums = 7, findValue = 9–7=2, containsKey(findValue) = true, result[1] = 1, result[0] = map.get(2), result = [0, 1]

return#

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

        for(int i = 0; i < nums.length; i++){
            int findValue = target - nums[i];
            if(map.containsKey(findValue)){
                result[1]=i;
                result[0]=map.get(findValue);
                return result;
            }
            map.put(nums[i],i);
        }
        return result;
    }
}

💡 為什麼要用HashMap？

📕 補充：Java常用的HashMap操作：