【LittleDuck_LeetCodeNote】01 - Two Sum

【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。

Question and Hints

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You can return the answer in any order.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Follow-up:

Can you come up with an algorithm that is less than O(n^2) time complexity?

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

⏰ Runtime: 14 ms (54.26%)

📦 Memory: 39.6 MB (100%)

Upgrade Solution

use Hash Table.

💡 建立一個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？

原先使用迴圈+陣列，在尋找裡面任何一個值時，第二個迴圈(j)都要從陣列的頭(index=0)開始尋找，萬一運氣不好都找不到正確的組合，就要移動第一個迴圈(i)再重跑一次。光是找其中一個值，花費的時間就有高機率到O(n)；這表示多數情況下，要找到正確的組合，時間複雜度必定會到O(nlogn)，最糟情況甚至會讓i和j都跑到底，來到O(n^2)的範圍。

HashMap的原理簡單來說，是用一個鍵值(key)對應一個被儲存的值(Value)，要尋找裡面任何一個值時，可以直接從對應的key值得到Value，其時間複雜度為O(1)；就算是Worst Case，也能在O(n)的範圍內找到正確的組合。

⏰ Runtime: 1ms (99.28%)

📦 Memory: 42.9 MB (39.20%)

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

添加 -> HashMap.put(key, value)
取值 -> HashMap.get(value)
刪除 -> HashMap.remove(value)
檢查索引是否成立 -> HashMap.containsKey(value)