0001. Two Sum - chasel2361/leetcode GitHub Wiki

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

最一開始的想法是硬幹，直接搜尋有沒有兩個數相加會等於target，然後把索引回傳

所以寫出來會變成這樣

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                total = nums[i] + nums[j]
                if total == target:
                    return [i, j]

這個寫法的問題是，在最糟的狀況下必須把所有數都掃過一遍才找到答案，時間複雜度會是O(N^2)，可以解決問題，但不是最好的解法，所以參考了大大的寫法之後變成這樣

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {} # [1]
        for i, num in enumerate(nums):
            if (target - num) not in numMap:
                numMap[num] = i # [2]
            else:
                return [numMap[target - num], i]

這個解法的重點在於檢視dict中是否含有target-num，若否便將num存入dict；若是則表示得到答案，利用dict的get函式即可取得索引

[1] 利用dict來儲存已經檢視過的num
[2] 將num作為key、i作為value存入numMap

如此一來最糟的狀況也只要把所有項目掃一遍就可以得到答案，時間複雜度為O(N)。

另外，如果數列有排序的話，就可以使用pointer來解，先從左到右取i，再從右到左取j，若兩者之和太大就把j向左移，直到i > j或和為零。

Code Link