LeetCode 解題筆記：1. Two Sum

作者：王一哲
日期：2026年6月5日


LeetCode 題目連結：1. Two Sum

解題想法

簡單難度的題目。可以用兩層 for 迴圈掃過所有從 $nums$ 取 2 個數字相加，時間複雜度 $O(n^2)$。

可以配合二分搜尋法將時間複雜度降成 $O(n log n)$。先將 $nums$ 的值 $num$ 及索引值 $i$ 組合成 tuple 存入串列 $arr$，將 $arr$ 依照 $num$ 排序，再取出排序後的值存成串列 sorted_nums 用於二分搜尋法。用一層 for 迴圈掃過 sorted_nums，其中第 $i$ 個值對應的目標值為 new_target = target - sorted_nums[i]，用 bisect_left 於 sorted_nums 之中搜尋 new_target，如果有找到 new_target，再從 $arr$ 之中找出對應 $nums$ 的索引值並回傳答案。

Python 程式碼

$O(n^2)$ 解。Runtime: 1719 ms, beats 25.03%. Memory: 19.81 MB, beats 74.11%.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # O(n**2) 暴力解
        n = len(nums)
        for i in range(n-1):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        # 預設的回傳值，題目保證有解，用不到
        return [-1, -1]

$O(n log n)$ 解。Runtime: 7 ms, beats 34.41%. Memory: 20.80 MB, beats 8.08%.

from bisect import bisect_left

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # O(n log n) 解
        arr = [(num, i) for i, num in enumerate(nums)]  # 取出值 num 及索引值 i
        arr.sort()  # 排序
        sorted_nums = [num for num, _ in arr]  # 取出排序後的值，用於二分搜
        n = len(nums)
        for i in range(n-1):
            new_target = target - sorted_nums[i]
            j = bisect_left(sorted_nums, new_target, i+1)
            if j < n and sorted_nums[j] == new_target:
                return [arr[i][1], arr[j][1]]
        # 預設的回傳值，題目保證有解，用不到
        return [-1, -1]

C++ 程式碼

$O(n^2)$ 解。Runtime: 35 ms, beats 34.48%. Memory: 14.18 MB, beats 68.74%.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // O(n**2) 解
        int n = (int)nums.size();
        for(int i=0; i<n-1; i++) {
            for(int j=i+1; j<n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        // 預設的回傳值，題目保證有解，用不到
        return {-1, -1};
    }
};

$O(n log n)$ 解。Runtime: 4 ms, beats 51.36%. Memory: 15.12 MB, beats 9.86%.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // O(n log n) 解
        int n = (int)nums.size();
        vector<pair<int, int>> arr (n);  // 取出值 num 及索引值 i
        for(int i=0; i<n; i++) {
            arr[i] = make_pair(nums[i], i);
        }
        sort(arr.begin(), arr.end());  // 排序
        vector<int> sorted_nums (n);  // 取出排序後的值，用於二分搜
        for(int i=0; i<n; i++) {
            sorted_nums[i] = arr[i].first;
        }
        for(int i=0; i<n-1; i++) {
            int new_target = target - sorted_nums[i];
            int j = lower_bound(sorted_nums.begin() + i + 1, sorted_nums.end(), new_target) - sorted_nums.begin();
            if (j < n && sorted_nums[j] == new_target) {
                return {arr[i].second, arr[j].second};
            }
        }
        // 預設的回傳值，題目保證有解，用不到
        return {-1, -1};
    }
};