[Day 29] Leetcode 15. 3Sum (C++)

前言

到了倒数第二天啦~ 大概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

结语

明天就是最後一天了~ 应该要好好来个感言，只能说这一系列绝对不是终点，刷题是保持手感的方式，但还有更多更多需要补充的知识，接下来就希望都可以有恒心毅力的完成各个里程碑罗。