模块一——双指针：18.四数之和

题目描述

题目链接：18.四数之和

算法原理

排序+双指针

• 依次固定?个数a ；
• 在这个数a 的后?区间上，利?「三数之和」找到三个数，使这三个数的和等于target - a 即可。
  PS：没做过三数之和的同学建议先去做一下三数之和再来做这道题。

代码实现

排序+双指针

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> vv;
        sort(nums.begin(),nums.end()); //1.排序
        
        for(int i = 0;i < n;)//2.固定一个数
        {
            for(int j = i + 1;j < n;)//3.固定三数之和的第一个数
            {
                int left = j + 1,right = n - 1;
                long long sum = (long long)target - nums[i] - nums[j];
                while(left < right)
                {
                    long long tmp =(long long) nums[left] + nums[right];
                    if(tmp > sum)right--;
                    else if(tmp < sum)left++;
                    else
                    {
                        vv.push_back({nums[i],nums[j],nums[left],nums[right]});
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left - 1])left++;//去重left
                        while(left < right && nums[right] == nums[right + 1])right--;//去重right
                    }
                }
                ++j;
                while(j < n && nums[j] == nums[j - 1])++j;//去重j
            }
            ++i;
            while(i < n && nums[i] == nums[i - 1])++i;//去重i
        }
        return vv;
    }
};

复杂度分析

时间复杂度：O(N³)

其中N是数组的长度。排序的时间复杂度是 O(Nlog?N)，枚举四元组的时间复杂度是O(N³)，因此总时间复杂度为 O(N³+Nlog?N)=O(N³)。

空间复杂度：O(log?N)或者O(N)

其中N是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组nums的副本并排序，空间复杂度为O(N)。