【优选算法】8----四数之和

有看过我上篇算法博客并且去做过的铁子们，对这道题的话应该就不会那么陌生了，因为这两道题

的解题思路有着异曲同工之妙~

-----------------------------------------begin-------------------------------------

题目解析：

跟三数之和就多了一数，看过的铁子还是很容易理解的~

讲解算法原理：

同三数之和一样，暴力算法肯定不得行的~

所以就直接在暴力算法的基础上，我们借助在三数之和的算法原理来多加一层循环，便解决这道四

数之和啦~

编写代码：

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

        for (int i = 0; i < n; ) 
        {
            for (int j = i + 1; j < n; ) 
            {
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right) 
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) 
                    {
                        left++;
                    } 
                    else if (sum > aim) 
                    {
                        right--;
                    } 
                    else 
                    {
                        ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                        while (left < right && nums[left] == nums[left - 1]) 
                        {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) 
                        {
                            right--;
                        }
                    }
                }
                j++;
                while(j<n&&nums[j]==nums[j-1])
                {
                    j++;
                }
            }
            i++;
            while(i<n&&nums[i]==nums[i-1])
            {
                i++;
            }
        }
        return ret;
    }
};

与三数之和有着异曲同工之妙~

题目直达->

18. 四数之和 - 力扣（LeetCode）

-----------------------------------------end---------------------------------------