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

給定一個整數陣列 nums 和一個整數目標，返回兩個數字的索引，使它們加起來等於目標。

您可以假設每個輸入都只有一個解決方案，並且您不會使用相同的元素兩次。

您可以按任何順序返回答案。

範例1:

輸入: nums = [2,7,11,15], target = 9
輸出: [0,1]
解釋: 因為 nums[0] + nums[1] == 9，回傳 [0, 1]。

範例2:

輸入: nums = [3,2,4], target = 6
輸出: [1,2]

範例3:

輸入: nums = [3,3], target = 6
輸出: [0,1]

限制:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只有存在一個有效的答案。

後續行動: 你能想出一個小於 O(n²) 時間複雜度的算法嗎？

失敗的解決辦法

以範例1為例
我一開始最簡單的想法是一個一個找

2 + 7 = 9
2 + 11 = 13
2 + 15 = 17
7 + 11 = 18
7 + 15 = 22
...以此類推

但效能不佳，會超時

解決辦法1

二分搜尋演算法 簡易說明

將資料排序好，一直找中間的資料，直到找到為止
例如: 1~9找9的過程

1~9
中間為 1 + (9 - 1) / 2 = 5
5 < 9
尋找 6~9

6~9
中間為 6 + (9 - 6) / 2 = 7.5
取小於 7.5 的 7
7 < 9
尋找 8~9

8~9
中間為 8
8 < 9
尋找 9~9

9~9 找到 9

詳細的步驟請到最下方參考連結了解更多

解答

python

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        """使用二分搜尋演算法取得整數串列的兩個數和為 target

        Args:
            nums (list[int]): 整數串列
            target (int): 目標

        Returns:
            list[int]: 兩個數的索引
        """

        # 將 nums 排序
        enum_nums = enumerate(nums)
        sorted_enum_nums = sorted(enum_nums, key=lambda num: num[1])

        for index in range(len(sorted_enum_nums)):
            left = index + 1
            right = len(nums) - 1

            while left <= right:
                middle = left + (right - left) // 2
                current_sum = sorted_enum_nums[index][1] + sorted_enum_nums[middle][1]

                if current_sum == target:
                    return [sorted_enum_nums[index][0], sorted_enum_nums[middle][0]]
                elif current_sum < target:
                    left = middle + 1
                elif current_sum > target:
                    right = middle - 1

        # 找不到回傳空串列
        return []

解決辦法2

以下簡稱 nums 串列裡面的每個值為 num
建立一個 records 字典存取找過的值，存取的方式為鍵為 num，值為 num index

records = {
    num: index
}

然後看 target - num 是否有在字典裡

以範例1為例，為了方便說明，次數從0開始算起

第0次

records = {}

9 - 2 = 7
不在 records

records = {
    2: 0
}
------------------
第1次

records = {
    2: 0
}

9 - 7 = 2
找到 records 存在 key = 2
回傳 [records[2], 1]
也就是 [0, 1]

假設找不到的話，那 records 就會再存一個

records = {
    2: 0,
    7: 1
}

解答

python

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        """使用 records 字典，記錄找過的值，以降低效能

        Args:
            nums (list[int]): 整數串列
            target (int): 目標

        Returns:
            list[int]: 兩個數的索引
        """

        # 記錄找過的值
        # key = nums value
        # value = nums index
        records = {}

        for index, value in enumerate(nums):
            # 期望找到的數值
            expected_value = target - value

            if expected_value in records:
                return [records[expected_value], index]

            records[value] = index

        # 找不到回傳空串列
        return []

結論

解決辦法2比較簡短，可讀性比較好，雖然測試運行結果比解決辦法1慢一點點
不過以維護上來說，我會選擇解決辦法2

參考

• 二分搜尋演算法