1. Two Sum

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

規則

給一組陣列以及 target，回傳某兩數 index 相加等於 target 數。

測試案例

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]

思路

  1. 透過步進雙層迴圈來查找符合條件 index
  2. 透過 dict 方式 (hashmap) 優化

實作

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 執行迴圈1
        for i1, a in enumerate(nums):
            # 執行迴圈2
            for i2, b in enumerate(nums):
                # 根據規則每個數只能用一次，遇到相同則跳過;
                if a == b:
                    continue
                # 符合條件則返回
                if a + b == target:
                    return [i1, i2]
        return []

這樣其實就已經解決了，但會發現時間複雜度達到 n*n -> O(n^2)，這屬於暴力解法，我們可以透過 hashmap 的行為進行優化:

values = {} # 創建 dict
for i, num in enumerate(nums):
    values[num] = i # 儲存數與 index

下一步進行添加判斷與規則

for i, num in enumerate(nums):
    diff = target - num # 查出差值
    if diff in values: # 如果有儲存在 hash 表內則返回結果
        return [values[diff], i]
    values[num] = i # 反之則儲存數與 index
return []

完整代碼

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        values = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in values:
                return [values[diff], i]
            values[num] = i
        return []