Разбор алгоритма Two Sum: от наивного перебора к оптимизации

延續昨天講到的array，我們來看實際的應用吧! btw 因為這篇想延續昨天介紹的 Array，而且後面還會介紹其他解法，所以這次先專注在最直覺的暴力解喔 >< 題目敘述: 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] 為例,兩兩配對可以列出: 回想一下怎麼列出上面那6組配對的: 2,依序跟後面的 7、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 } }; 雙層迴圈的暴力解雖然容易理解,但當陣列很大時(例如 n = 10000),要檢查的組合數會逼近 10000^2 / 2 = 5000萬次,效率會變得很差。 有沒有辦法只掃描一次陣列，就找到答案呢？ 之後應該會有一篇專門講 Hash table，敬請期待~