0001. Two Sum (Easy)
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:
| |
| |
分析/解題
題目要求是，在一組陣列中找出兩個數，其加總恰等於給定值。
每個數不能被重複使用，且必剛好只有一個解。
像這種題目，由於被擺在第一題，大多數狀況都不會被拿來考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:
Python:
面試實際可能會遇到的問題
這裡有一個原則：
***不論是什麼問題，不論你當下想到的方法有多暴力有多爛，
有想到方法就先講沒關係。***以這題為例，你應該先提出最先的O(N²)解，大概描述完以後，
再說但這樣時間複雜度比較高，
如果應用HashMap(python用dict)的話，
可以讓每個數只需要花O(1)作搜尋，複雜度就會降到O(N)。
先講出一個可能的解法，再想辦法延伸修改或者改進它，
這是大多數公司建議(尤其Google)的方式，
一來可以讓面試官知道你不是腦袋空空，至少先有個基本分，
二來在講這個暴力解時，你可以有緩衝的時間去想更好的解法。
還有一些需要注意的東西可以做為你和面試官互動和溝通的部分，
或有可能是面試官問你的進一步問題，
在平常每題解完後，都應該留點時間給自己去思考一下可能的變化。
以此題為例：
「請問這個陣列是否是排序好的？」(排好的解法就又不同了XD)
「如果我想要的是回傳那兩個數字而非indices的話呢？」(修改pair即可)
「你剛剛提到了排序，那怎樣的狀況先對陣列作排序會比較好？」
「如果答案存在很多組，能否找出所有的解？」
「如果當中存在重覆的數字的話呢？」
「為什麼HashTable/HashMap的存取是O(1)？」(這可能就扯比較遠了XD)
「那麼它們的worst case呢？什麼狀況下會發生？」
從LeetCode學演算法，我們下次見囉，掰~