1. Two Sum

發表於 分類於 ， 閱讀次數： 文章字數： 1.4k

種類 : hash table
難度 : easy
題目 : 1. Two Sum

思維邏輯

  1. 歷遍list
    1. 若set中有 target - 當前值，返回index(使用value查index)
    2. 將值加入set中，待下一輪比較

解法

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        s = set()
        for i, value in enumerate(nums):
            if (target - value) in s:
                return [i, nums.index(target - value)]
            else:
                s.add(value)

時間複雜度: O(n)
空間複雜度: O(n)

難點

  1. dict無法儲存相同key、使用set時如何反向查index

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
"""
dict
若有相同key(e.g. [3, 3]): 在儲存前返回結果
"""
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        records = dict()

        for index, value in enumerate(nums):  
            if target - value in records:   # 遍历当前元素，并在map中寻找是否有匹配的key
                return [records[target- value], index]
            records[value] = index    # 如果没找到匹配对，就把访问过的元素和下标加入到map中
        return []

時間複雜度: O(n)
空間複雜度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
雙指針
排序後方可使用此解法
"""
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 对输入列表进行排序
        nums_sorted = sorted(nums)
        
        # 使用双指针
        left = 0
        right = len(nums_sorted) - 1
        while left < right:
            current_sum = nums_sorted[left] + nums_sorted[right]
            if current_sum == target:
                # 如果和等于目标数，则返回两个数的下标
                left_index = nums.index(nums_sorted[left])
                right_index = nums.index(nums_sorted[right])
                if left_index == right_index:
                    right_index = nums[left_index+1:].index(nums_sorted[right]) + left_index + 1
                return [left_index, right_index]
            elif current_sum < target:
                # 如果总和小于目标，则将左侧指针向右移动
                left += 1
            else:
                # 如果总和大于目标值，则将右指针向左移动
                right -= 1

時間複雜度: O(n)
空間複雜度: O(1)