iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 2
2
Software Development

從LeetCode學演算法系列 第 2

[Day 2] 從LeetCode學演算法 - 0001. Two Sum (Easy)

目標:
這題主要目的在於練習HashMap/Dictionary的應用。

原題:

Question:
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].

分析/解題:
題目要求是,在一組陣列中找出兩個數,其加總恰等於給定值。
每個數不能被重複使用,且必剛好只有一個解。
像這種題目,由於被擺在第一題,大多數狀況都不會被拿來考XD
但,凡事總有例外。
我們先來分析一下,如果按照原題的要求該怎麼解。
如果input長度為N,那麼暴力解就是將數字兩兩相加看是不是解,
這樣的解法要算N(N-1)/2次,也就是O(N²)的時間複雜度。

該怎麼降低複雜度呢?我們會希望每個數只要查一次就知道結果,
有沒有這樣的結構?當然有,在Java中可以用HashMap
而在Python中可以用dictionary

只要每一次從map中確認當下target-num是否在map中,
在的話就表示找到了,可以將結果取得,
沒找到的話,就將一組(num, index)放進map中,
依此流程,最壞的狀況整個array遍歷後,就可以得到答案。

時間複雜度:
由於HashMap在put和get最好的狀況都是O(1),
遍歷整個Map需要O(N)。

Java:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i};
            }
            map.put(nums[i], i);              
        }
        throw new IllegalArgumentException("No Answer");
    }
}

Python:

class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
        numMap = {}
        for i in range(len(nums)):
            if numMap.__contains__(target-nums[i]):
                return [numMap.get(target-nums[i]), i]
            else:
                numMap[nums[i]] = i

面試實際可能會遇到的問題:
這裡有一個原則:
不論是什麼問題,不論你當下想到的方法有多暴力有多爛,
有想到方法就先講沒關係。

以這題為例,你應該先提出最先的O(N²)解,大概描述完以後,
再說但這樣時間複雜度比較高,
如果應用HashMap(python用dict)的話,
可以讓每個數只需要花O(1)作搜尋,複雜度就會降到O(N)。

先講出一個可能的解法,再想辦法延伸修改或者改進它,
這是大多數公司建議(尤其Google)的方式,
一來可以讓面試官知道你不是腦袋空空,至少先有個基本分,
二來在講這個暴力解時,你可以有緩衝的時間去想更好的解法。

還有一些需要注意的東西可以做為你和面試官互動和溝通的部分,
或有可能是面試官問你的進一步問題,
在平常每題解完後,都應該留點時間給自己去思考一下可能的變化。
以此題為例:
「請問這個陣列是否是排序好的?」(排好的解法就又不同了XD)
「如果我想要的是回傳那兩個數字而非indices的話呢?」(修改pair即可)
「你剛剛提到了排序,那怎樣的狀況先對陣列作排序會比較好?」
「如果答案存在很多組,能否找出所有的解?」
「如果當中存在重覆的數字的話呢?」
「為什麼HashTable/HashMap的存取是O(1)?」(這可能就扯比較遠了XD)
「那麼它們的worst case呢?什麼狀況下會發生?」

從LeetCode學演算法,我們下次見囉,掰~


上一篇
[Day 1] 從LeetCode學演算法 - 緒論:你應該知道的面試基礎和解題技巧
下一篇
[Day 3] 從LeetCode學演算法 - 0014. Longest Common Prefix (Easy)
系列文
從LeetCode學演算法30
1
km101km
iT邦新手 5 級 ‧ 2019-09-03 18:05:24

希望每篇結尾可以預告下一天的leetcode題目
這樣讀者比較好準備

Desolve iT邦新手 5 級‧ 2019-09-03 20:01:27 檢舉

也行XD 明天是0014. Longest Common Prefix (Easy)

1
阿瑜
iT邦新手 4 級 ‧ 2019-10-08 16:15:18

大學的時候 都是 刷 UVa(CPE)。
看完文章,覺得 刷題也能很有系統,不僅是難度上還有思維。
之前 解完,就下一題,很少會去想如何讓他 複雜度下降,以及 其他題目相關的變形。
趁著 碩一有時間也來好好學學,謝謝你的文章,很棒推推 /images/emoticon/emoticon12.gif

1
阿瑜
iT邦新手 4 級 ‧ 2019-10-08 16:33:48

在語法的部分,長知識啦 ~~~ XD

    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
    # 註解 回傳值 & 註解 參數 : ''

還有

    if numMap.__contains__(target-nums[i]):
    # 我之前都用 has_key() ,看了文章之後,發現 還有 __contains__ 的用法 

我要留言

立即登入留言