题目描述

三数之和

代码解析

暴力

在做这一道题的时候，脑海里先想出来的是暴力方法，一次排序，将这个数组变为有序的，再通过三次for循环来寻找满足条件的数字，然后将符合条件的数组与之前符合条件的数组进行一一对比，来完成去重的目的，时间复杂度光是三层for循环就达到了n^3，再加上一个sort和count函数，nlogn + mn^3。

class Solution {
public:

    bool chech(int a, int b, int c)
    {
        return a + b + c == 0;
    }

    vector<vector<int>> threeSum(vector<int>& na) {
        vector<vector<int>> ans;
        int n = na.size();
        sort(na.begin(), na.end());
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int k = j + 1; k < n; k++)
                {
                    if (chech(na[i], na[k], na[j]))
                    {
                        vector<int> a(3, 0);
                        a[0] = na[i];
                        a[1] = na[j];
                        a[2] = na[k];

                        if (count(ans.begin(), ans.end(), a) == 0)
                            ans.push_back(a);
                    }
                }
            }
        }

        return ans;
    }
};

---

优化

这个时候要想代码如何进行优化，如何把判重的count和后两层循环给优化了，这样就能把时间复杂度从nlogn + mn^3降低到nlogn + n^2。

要找一个满足条件的三个数，我们可以先固定一个数字，然后就可以只考虑除固定数字之外的区间了，在另一个区间可以找两个指针l和r，如果说l指针指向的数字+r指针指向的数字，等于 事前固定的数字的相反数，就可以达到题目要求了。

如果说l+r > -i，说明r太大，r--；或者说是r + l > -i，说明l太小，l++。当l和r相交的时候依旧没有找到答案，就说明i在某个固定的位置是没有解的，将i++，即可。然后继续在l和r区间寻找符合题意的数字。

题目要求不能有重复的，什么情况下会出现重读的？当l + r == -i的时候，l的下一位或者r的上一位跟l或r本身是相同的，就说明出现了重复的情况，也有可能是i跟i的下一位相同。所以可以以此为条件，来进行去重。也可以将所有符合题意的答案都加入到一个数组当中，然后使用去重算法，也可以达到去重的目的。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < n;)
        {
            
            if (nums[i] > 0) break;
            int l = i + 1, r = n - 1;
            int t = -nums[i];
            while (l < r)
            {
                int sum = nums[l] + nums[r];
                if (sum > t) r--;
                else if (sum < t) l++;
                else 
                {
                    res.push_back({nums[l], nums[r], nums[i]});
                    l++, r--;
                    while (l < r && nums[l] == nums[l - 1])
                    {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r + 1]) 
                    {
                        r--;
                    }
                }
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
            
        }
        return res;
    }
};

 

扩展

四数之和

四数之和和三数之和的代码类似，可以当练习做一下。 

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();

        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n ; )
        {
            for (int j = i + 1; j < n; )
            {
                int l = j + 1;
                int r = n - 1;
                long long tmp = nums[i] + nums[j];
                long long t = target - tmp;
                while (l < r)
                {
                    if ((long long)(nums[l] + nums[r]) > t) r--;
                    else if ((long long)(nums[l] + nums[r]) < t) l++;
                    else {
                        res.push_back({nums[i], nums[j], nums[l], nums[r]});
                        l++;
                        r--;
                        while (l < r && nums[l] == nums[l - 1])
                        {
                            l++;
                        }
                        while (l < r && nums[r] == nums[r + 1]) 
                        {
                            r--;
                        }
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return res;
    }
};