力扣四数之和去重问题


class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) { 
        sort(nums.begin(),nums.end());
        vector<vector<int>>res;
        if(nums.size()<4)
        return res;
        for(int i=0;i<nums.size()-3;i++){
            int a=i;
            for(int j=i+1;j<nums.size()-2;j++){ 
                int b=j;
                int c=j+1,d=nums.size()-1;
                while(c!=d){
                    if(nums[c]+nums[d]==target-nums[a]-nums[b]){
                        vector<int>tmp;
                        tmp.push_back(nums[a]);
                        tmp.push_back(nums[b]);
                        tmp.push_back(nums[c]);
                        tmp.push_back(nums[d]);
                        sort(tmp.begin(),tmp.end());
                        if(res.size()>=1&&tmp!=res[res.size()-1])
                        res.push_back(tmp);
                        if(res.size()<1)
                        res.push_back(tmp);
                        break;
                    }
                    else if(nums[c]+nums[d]<-nums[a]-nums[b]){
                        c++;
                    }
                    else d--;
                }
            }
        }
        return res;
    }
};

四树之和，为什么数据为[-3,-1,0,2,4,5]
2时无结果
去重：如果该数组与上一个相同则不放入

全网最详细的博客：

力扣18-四数之和-java_初遇见的博客-CSDN博客题目描述给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。题意：这道题是求四个数的和相加等于目标值，然后要把重复的值去掉。这个题的思路和力扣15-三数之和的思路类似，三数之和是固定一个数，其余进行双指针。四数之和是固定两个数，其余进行双指针。排序后如图所示，然后用i,j来固定两个数

https://blog.csdn.net/weixin_44591656/article/details/115045212

问题出在这里：

if (res.size() >= 1 && tmp != res[res.size() - 1])
    res.push_back(tmp);
if (res.size() < 1)
    res.push_back(tmp);

这个部分处理了将结果 tmp 加入到结果数组 res 的逻辑。但是，这样的处理方式会导致结果数组中出现重复的解。当程序执行到 res.push_back(tmp); 这里时，不管之前的 res 是否已经有结果，都会将 tmp 加入到 res 中。这样就会导致重复的解出现在结果数组中。

正确的做法应该是在 tmp 加入到 res 之前先进行去重处理，判断 tmp 是否已经在 res 中存在，如果不存在才将其加入。可以通过使用 std::find 函数来实现去重：

if (res.empty() || std::find(res.begin(), res.end(), tmp) == res.end())
    res.push_back(tmp);

这样做就可以确保结果数组 res 中不会出现重复的解了。

修正后的代码如下：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) { 
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        if (nums.size() < 4)
            return res;
        for (int i = 0; i < nums.size() - 3; i++) {
            for (int j = i + 1; j < nums.size() - 2; j++) { 
                int c = j + 1, d = nums.size() - 1;
                while (c < d) {
                    if (nums[i] + nums[j] + nums[c] + nums[d] == target) {
                        vector<int> tmp = {nums[i], nums[j], nums[c], nums[d]};
                        res.push_back(tmp);
                        while (c < d && nums[c] == tmp[2]) c++;
                        while (c < d && nums[d] == tmp[3]) d--;
                    }
                    else if (nums[i] + nums[j] + nums[c] + nums[d] < target) {
                        c++;
                    }
                    else {
                        d--;
                    }
                }
                while (j + 1 < nums.size() - 2 && nums[j + 1] == nums[j]) j++;
            }
            while (i + 1 < nums.size() - 3 && nums[i + 1] == nums[i]) i++;
        }
        return res;
    }
};

不知道你这个问题是否已经解决, 如果还没有解决的话:

这篇博客: ❤️导图整理数组5: 四数之和相比三数之和的大量优化, 力扣18详细注解❤️中的 0.导图整理 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^