前言

到了倒數第二天啦~ 大概Day 21開始有一系列的sum題目，一直說要接續完成，終於今天又回歸了─也是top 100 liked中的sum題目─15. 3Sum。就來一起看看吧！

想法

如果還沒寫過1. Two Sum，請先去寫寫看，畢竟這是leetcode的天字號第一題XD 就是那題使用hash table讓我開始感受到原來寫法有這麼多種，而不是死腦袋的窮舉兩個for迴圈去找答案。
而看到這題3sum，第一個想法就是固定第一個數字，後面想採用2sum來解決，不過結果證明一定需要優化，如果只是盲目地遍歷第一個數然後後面直接採用2sum，就會time limit exceed給你看XD
那我們就來看有哪些優化方式。

• 排序
  首先題目要求的是三個不重複的數組合。我們可以藉由排序的方式來省去一些重複的檢查，不過排序基本上就需要O(nlogn)的時間。
  而再來我們來一一檢視可以優化的地方。
• 第一個數
  首先在遍歷第一個數的時候，如果有重複的數，第二次遇到就可以跳過了，因為該組合在第一次遇到的時候就必定包含了。另外，因為加總要=0，三個數的正負情形不外乎是-,-,+，-,0,+或-,+,+，0,0,0，沒有了。我們可以觀察到第一個數必定<=0，因此如果發現第一個數遍歷到正數了，那也可以提早結束搜尋了。
• 第二、三個數
  而針對第二個數與第三個數，因為也排序過了，就可以採用雙指針的方式，從第一個數往後的範圍，第二個數從小的開始找，第三個數從大的開始找，開始逼近找到答案。而要注意的是為了要避免重複的組合，當我們找到一組解之後，下一個組合的第二數或第三數就要直接到到下一個不一樣的數，跳過重複的部分。
  把以上的條件都用程式寫出來後，其實也就完成了，如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        // note this!
        int n=nums.size();
        // sort the number
        sort(nums.begin(), nums.end());
        // the first number
        int target;
        // fix one number and use 2 pointers to look for answer
        for(int i=0;i<n-2;++i){
            // if the first is positive, can stop now
            if(nums[i]>0){
                break;
            }
            // if the first one is equal to the previous, can skip
            if(i>0 && nums[i]==-target){
                continue;
            }
            // use two pointer to search for the answer
            target = -nums[i];
            int l = i+1;
            int r = nums.size()-1;
            while(l<r){       
                if((nums[l]+nums[r])==target){
                    ans.push_back({-target, nums[l], nums[r]});
                    // skip the same number as previous one
                    while(l<n-1 && nums[l+1]==nums[l]){
                        ++l;
                    }
                    while(r>0 && nums[r-1]==nums[r]){
                        --r;
                    }
                    ++l;
                    --r;
                }
                // too big, turn left
                else if((nums[l]+nums[r])>target){
                    --r;
                }
                // too small, turn right
                else{
                    ++l;
                }
                
            }
            
        }
        return ans;
    }
};

• 注意
  其中有一個可以注意一下的地方，如果我在以上程式中用到n的地方直接拿nums.size()來取代，在for(int i=0;i<n-2;++i)這裡跟l<n-1都會出問題的。因為若現在nums是一個空vector或是只有一個數的vector，我拿nums.size()-2，會變成undefined的數。這是因為nums.size()是一個size_t的型別，等於unsigned int，值的範圍是0 到 4,294,967,295，是沒有負數的，我將它-2的話，會變成未定義的數！所以要讓它可以變負數使用的話，必須先把它轉為int來存。

如果超過3sum，而是更多sum的時候，我就會選擇採用dfs或是[Day 24] Leetcode 416. Partition Equal Subset Sum (C++)提到的DP方式來完成了。
這題完成之後，我們大概也把top 100 liked中sum相關的基本題目解決啦！還有一題hard的124. Binary Tree Maximum Path Sum或許明天就來以這題完美收尾吧~ XD

結語

明天就是最後一天了~ 應該要好好來個感言，只能說這一系列絕對不是終點，刷題是保持手感的方式，但還有更多更多需要補充的知識，接下來就希望都可以有恆心毅力的完成各個里程碑囉。