題目資訊

• 題目編號: 1
• 題目連結: Two Sum
• 主題: Array, Hash Table

題目敘述

給定一個整數陣列 nums 和一個整數 target，請回傳_兩個數字的索引，使它們相加等於 target_。

你可以假設每個輸入都會有**_唯一_的解答**，並且你不能重複使用_相同的_元素。

你可以以任意順序回傳答案。

範例 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 \leq \text{nums.length} \leq 10^4$
• $-10^9 \leq \text{nums}[i] \leq 10^9$
• $-10^9 \leq \text{target} \leq 10^9$
• 只存在一個有效的答案。

進階: 你能否提出一個時間複雜度小於 $O(n^2)$ 的演算法？

直覺

這個問題是一個典型的 “兩數之和” 問題，要求在數組中找到兩個不同的元素，使其和等於指定的目標值。鑑於問題的約束條件，確保總會有且只有一個解，且元素不能重複使用，我們的初步想法是系統性地遍歷數組以識別其和等於目標值的數字對。這意味著直接比較數組中的每個數字與其他數字，以找到互補對的簡單方法。

解法

解法的步驟如下：

1. 初始化結果容器：首先定義一個容器（向量 result），用於存儲這兩個數字的索引，這兩個數字的和等於目標值。

2. 遍歷數組：使用一個迴圈從第一個元素遍歷到倒數第二個元素。這是為了選擇數字對中的第一個數字。

3. 尋找互補數：對於索引 i 處的每個數字，計算其互補數為 target - nums[i]。這個互補數表示與 nums[i] 共同組成目標和所需的值。

4. 搜尋互補數：利用標準函式庫中的 find 函數，自索引 i + 1 起的子數組中搜尋這個互補數，直到數組結尾。這確保我們不重複使用同一個元素組成數字對，符合問題的限制。

5. 驗證互補數：如果找到了互補數，find 會返回其索引，否則返回數組的終端迭代器。檢查找到的互補數索引是否有效（即，不等於數組的大小）。

6. 存儲結果並終止：若找到有效的互補數，將索引 i 和 complementIndex 保存到 result 向量中，並終止迴圈，因為問題保證只有一個解。

7. 返回結果：最後，返回包含兩個數字索引的 result 向量，其總和等於目標值。

此方法雖然簡單，但在問題的約束條件下有效地運作。通過利用 find 函數直接實現解決方案的搜尋，同時本質上遵循不重複使用同一元素的限制，並假設確實存在唯一解。

程式碼

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        
        // 遍歷陣列中的數字，但不包含最後一個
        for (int i = 0; i < nums.size() - 1; i++) {
            // 找出補數的索引，使得該補數和nums[i]一起加總為目標值
            int complementIndex = find(nums.begin() + i + 1, nums.end(), target - nums[i]) - nums.begin();
            
            // 如果找到有效的索引，則儲存該索引並中斷迴圈
            if (complementIndex != nums.size()) {
                result.push_back(i);
                result.push_back(complementIndex);
                break; // 我們假設只有一個解答
            }
        }
        
        return result;
    }
};

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        
        # 迭代陣列中的數字，但不包括最後一個
        for i in range(len(nums) - 1):
            # 找出和 nums[i] 一起加起來等於 target 的補數的索引
            complementIndex = nums.index(target - nums[i], i + 1)
            
            # 如果找到有效的索引，存儲索引並退出迴圈
            if complementIndex != len(nums):
                result.append(i)
                result.append(complementIndex)
                break  # 我們假設只有一個解
        
        return result

複雜度分析

• 時間複雜度: $O(n^2)$

  該演算法主要包括一個單一迴圈，並且在每次迭代中調用一次 find 函數。這個 find 函數的時間複雜度為 $O(n)$，因為在最壞的情況下，它可能需要遍歷向量 nums 中幾乎所有剩餘的元素來找到補數。由於外層迴圈也迭代 $O(n)$ 次，因此整個演算法的時間複雜度是 $O(n) \times O(n) = O(n^2)$。

• 空間複雜度: $O(1)$

  空間複雜度為 $O(1)$ 是因為該演算法使用了固定數量的額外空間。儘管使用了一個向量 result 來儲存索引，但這個向量的大小是固定的（最多2個元素，因為根據問題的要求只需儲存一個有效解的兩個索引）。因此，額外空間不會隨著輸入大小而變化，並且保持不變。