双指针(8)_单调性_四数之和

个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

双指针(8)_单调性_四数之和

收录于专栏【经典算法练习】
本专栏旨在分享学习C++的一点学习笔记，欢迎大家在评论区交流讨论💌

目录

1. 题目链接:

2.题目描述 :

3.解法 :

    解法一(暴力枚举) :

    算法思路 :

    代码展示 :

    结果分析 :

    解法二(排序 + 双指针) :

    算法思路 :

    图解流程 :

    代码展示 :

    结果分析 :

4.总结 :

温馨提示: 大家没看三数之和这道题可以先去了解一下,思路基本一样

双指针(7)_单调性_三数之和-CSDN博客

1. 题目链接:

OJ链接-----. - 力扣（LeetCode）

2.题目描述 :

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

3.解法 :

    解法一(暴力枚举) :

    算法思路 :

这里的暴力枚举非常朴实无华,就是排序 + 四层循环 + set去重

这里简单分析一下时间复杂度:

这个暴力枚举时间复杂度为O(N^4),题目数组的数据范围是在200之内,所以暴力枚举数据级别可达1.6*10^9,绝对是过不了这道题的

算法题的数据范围就是这样,你的暴力算法永远只差一点,而要去达到这一点需要去更改其他算法去简化我们的暴力算法.

    代码展示 :

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        set<vector<int>> T;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
                for(int k = j + 1; k < n; k++)
                    for(int l = k + 1; l < n; l++)
                    {
                        long long sum = (long long)nums[i] + nums[j] + nums[k] + nums[l];
                        if(sum == target) T.insert({nums[i], nums[j], nums[k], nums[l]});
                    }

        vector<vector<int>> ret(T.begin(), T.end());
        return ret;
    }
};

    结果分析 :

在我们意料之中,暴力算法只差6个例子就能顺利通过!!!

但是这次暴力算法对我们还是有收获的,在我们遇到第283个例子时,我们发现,数据溢出的问题,这是我们开始没有想到的,因为例子中这四个数相加会超出int的范围(爆int),所以后面我就使用long long进行存贮,这为后面我们的优化算法进行了提醒

这次的爆int其实并不是空穴来风的,我们之前看算法题时,只会看它的数组数据范围,没有看过数组中数据的范围,在这道题目中,每个数是在10^9范围之内,而我们的int的数据范围为[-2147483648, 2147483647]之间,也就是大概2*10^9,我们这里四个数相加肯定是爆了int,这也是算法题惯用的伎俩.

    解法二(排序 + 双指针) :

强烈推荐大家先去看一下三数之和这道题,思路基本一样

双指针(7)_单调性_三数之和-CSDN博客

    算法思路 :

a. 依次固定一个数a;

b. 在这个数a的后面区间上,利用[三数之和]找到三个数,使这三个数的和等于target - a即可.

    图解流程 :

详细的细节问题已经在三数之和中讲解过,这里就不再多说:

总结:

1. 依次固定一个数a;
2. 在a后面的区间内,利用"三数之和"找到三个数使这三个数的和等于target - a即可
   1. 依次固定一个数b;
   2. 在b后面的区间内,利用双指针找到两个数,

使这两个数的和等于target - a -b即可.

    代码展示 :

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 sum = (long long)target - nums[i] - nums[j];
                while(left < right)
                {
                    if(nums[left] + nums[right] > sum) right--;
                    else if(nums[left] + nums[right] < sum) left++;
                    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;
    }
};

    结果分析 :

顺利通过!!!

时间复杂度分析:

外层两层for循环,内层一层while循环,总的时间复杂度为O(N^3)

空间复杂度分析:
排序的sort出战压栈会占用空间(底层用的是快排)O(logN),其他设置的常量可以忽略不记,总的时间复杂度还是O(logN)

4.总结 :

无论是两数之和,三数之和或者是四数之和它们的共同思想都是一样的,都是先经过排序,使得数组中的数有序,在利用数组中的单调性使用双指针算法进行求解. 

好了,双指针系类完结撒花,下面一个专题是滑动窗口问题,感兴趣的宝子们赶紧点赞关注收藏起来吧!

欢迎 点赞👍 收藏✨ 留言✉ 加关注💓

大家也可以关注我的算法专栏[经典算法练习]

我们明天见!!!