18. 四数之和 c++ 防止溢出

题目描述

给你一个由 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

思路：

 三数之和见：15. 三数之和 c++__会飞的鲨鱼的博客-CSDN博客
 如果前面的三数之和会做了的话，这里其实就是在前面的基础上多添加一个遍历的指针而已。
 会做三数之和的可以不用看下面的了。。
  
 使用四个指针(i  保存使得nums[i]+nums[j]+nums[c]+nums[d]==target的解。偏大时d左移，偏小时c右移。c和d相
 遇时，表示以当前的a和b为最小值的解已经全部求得。j++,进入下一轮循环b循环，当j循环结束后。
 i++，进入下一轮a循环。 即(i在最外层循环，里面嵌套j循环，再嵌套双指针c,d包夹求解)。
准备工作：

 因为要使用双指针的方法，排序是必须要做der~。 时间复杂度O(NlogN).
解决重复解：

 上面的解法存在重复解的原因是因为移动指针时可能出现重复数字的情况。所以我们要确保移动指针后，
 对应的数字要发生改变才行哦。
时间复杂度：

a遍历O(N)里嵌套b遍历O(N)再嵌套c,d双指针O(N)--> O(N^3)。 总比暴力法O(N^4)好些吧。

作者：misakasagiri-2
链接：https://leetcode.cn/problems/4sum/solution/shuang-zhi-zhen-jie-fa-can-zhao-san-shu-zhi-he-ge-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

c++代码 

class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        
        vector> res;
        int n=nums.size();
        int i,j,c,d;
        long long t,t2;
        if(n<4){
            return res;
        }else{
            sort(nums.begin(),nums.end());
            for(i=0;i0&&nums[i]==nums[i-1]){
                    continue;
                }else{
                    for(j=i+1;ji+1&&nums[j]==nums[j-1]){
                            continue;
                        }else{
                            c=j+1;d=n-1;
                            while(ct2){
                                    d--;
                                }else{
                                    res.push_back({nums[i],nums[j],nums[c],nums[d]});
                                    while(c

欢迎分享，转载请注明来源：内存溢出

原文地址: https://www.outofmemory.cn/langs/2990909.html