日期：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]
