延續昨天講到的array，我們來看實際的應用吧!
btw 因為這篇想延續昨天介紹的 Array，而且後面還會介紹其他解法，所以這次先專注在最直覺的暴力解喔 ><

Two Sum

題目敘述:
LeetCode 1. Two Sum

You are 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，以及一個整數 target，請找出陣列中兩個數字，使它們的和等於 target，並回傳這兩個數字的索引（index）。

你可以假設每組輸入都恰好只有一組解答，而且同一個元素不能被使用兩次。

答案的回傳順序不限。(即 [ 0 , 1 ] 或 [ 1 , 0 ] 都可以)

範例測資:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

思考過程 : 先不管效率,怎麼「暴力」解?

拿到這種題目,第一步不是急著想效率最好的解法,而是先想最直覺的做法能不能解出來,之後再來優化。

要確認 陣列裡有沒有兩個數字加起來等於target ，最直覺的做法就是:把每一種可能的兩個數字組合都試一遍。

以 [2, 7, 11, 15] 為例,兩兩配對可以列出:

• 2+7=9、2+11=13、2+15=17
• 7+11=18、7+15=22
• 11+15=26
  總共 6 種組合(4個數字兩兩配對,共 C4取2=4*3/2=6 種)。

回想一下怎麼列出上面那6組配對的:

• 先固定第一個數字是 2,依序跟後面的 7、11、15 相加
• 再固定第一個數字是 7,依序跟後面的 11、15 相加
• 再固定第一個數字是 11,跟後面的 15 相加

這個「固定一個數字,再跟後面每一個數字配對」的過程,天生就需要兩層迴圈:
外層負責「換固定的那個數字」,內層負責「跟後面每一個數字依序配對相加」。

i=0 j=i+1

然後i=0 j=1的時候target=9迴圈就已經結束了，這邊只是幫助理解才會繼續放動畫喔 !
i=1 j=2

i=2 j=3

為什麼內層迴圈從 i+1 開始？

因為：

• 不需要自己跟自己配對
• 避免重複計算

例如：

[2,7 ] 和 [ 7 , 2 ] 其實是同一組配對，所以直接往後找就好

完整程式碼

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
 
        int n = nums.size();                     // 取得陣列長度
 
        for (int i = 0; i < n; i++) {             // 外層:固定第一個數字
            int x = nums[i];                      // x 是目前固定的數字
 
            for (int j = i + 1; j < n; j++) {     // 內層:從 i+1 開始,跟後面每個數字配對(避免重複配對)
                int y = nums[j];                  // y 是拿來配對的數字
                int a = x + y;                    // 計算這一組配對的總和
 
                if (a == target) {                // 如果總和剛好等於 target
                    return {i, j};                 // 回傳這兩個數字的索引,直接結束函式
                }
            }
        }
 
        return {};   // 如果雙層迴圈跑完都沒找到符合的配對,回傳空的 vector
    }
};

複雜度分析

• 時間複雜度:O(n²) — 最壞情況下,要檢查完所有 n(n-1)/2 種配對組合

雙層迴圈的暴力解雖然容易理解,但當陣列很大時(例如 n = 10000),要檢查的組合數會逼近 10000^2 / 2 = 5000萬次,效率會變得很差。

有沒有辦法只掃描一次陣列，就找到答案呢？
之後應該會有一篇專門講 Hash table，敬請期待~