leetcode 18. 4Sum KSum的解决办法

向右看齐 2022-06-09 07:55 137阅读 0赞

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = \[1, 0, -1, 0, -2, 2\], and target = 0.

A solution set is:  
\[  
\[-1, 0, 0, 1\],  
\[-2, -1, 1, 2\],  
\[-2, 0, 0, 2\]  
\]

题意很简单，这里就不多说了。这里做一个总结：

第一种方法是把KSum降低为K-1Sum，然后逐步降低，最后处理2Sum，这个可以通过**递归实现**，也可以通过**循环实现**，最后的2Sum是通过双指针遍历得到，但是要注意避免重复元素的计算。这里有一个小细节需要注意：**我们要寻找KSum的解，那么数组遍历范围是\[0,len-k+1)或者\[0,len-k\]，所以在降低k值的时候要注意遍历范围的计算；**

第二种是通过Hash实现，不过这个是针对4Sum的，针对KSum也可以类似处理，不过实现起来有点麻烦。思想主要就是把可能的2Sum之和存放到map中，然后通过双指针遍历map来实现**2Sum+2Sum=4Sum**。 这个问题的比较麻烦的地方是要注意处理重复的元素，因为index可能出现重复，index对应的value重复问题，可以在代码中看出，这个处理比较麻烦。这仅仅是4Sum就这么麻烦，要是针对KSum，要是使用Hash实现，那么处理的就更加麻烦了。

综合来说，我建议使用第一种方法，建议循环实现。

建议和这一道题[leetcode 454. 4Sum II][] 一起学习

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    
    public class Solution 
    {   
        /*
         * 通过吧KSum降低为K-1Sum，然后逐步降低，最后处理2Sum
         * 
         * */
        public List<List<Integer>> fourSumBBBB(int[] nums, int target)
        {
            Arrays.sort(nums);
            return kSum(nums, target, 3);
        }
    
        public List<List<Integer>> kSum(int[] nums, int target,int kSum)
        {
            List<Integer> one=new ArrayList<>();
            kSumByDG(kSum, nums, 0, nums.length-kSum+1, target, one);
            return finResList;
        }
    
        public void kSumByDG(int kSum,int[] nums,int beg ,int end,int target,List<Integer> one)
        {
            if(kSum==2)
            {
                int allSum=0;
                for(int i=0;i<one.size();i++)
                    allSum+=one.get(i);
                int left=beg,right=end;
                while(left < right)
                {
                    int ssum = allSum + nums[left]+nums[right];
                    if(ssum==target)
                    {
                        List<Integer> tmp = new ArrayList<>(one);
                        tmp.add(nums[left]);
                        tmp.add(nums[right]);
                        finResList.add(tmp);
                        while(left < right && nums[left]==nums[left+1]) left++;
                        while(left < right && nums[right]==nums[right-1]) right--;
                        left++;
                        right--;
                    }else if(ssum < target)
                        left++;
                    else
                        right--;
                }
                return ;
            }else
            {
                for(int i=beg;i<end;i++)
                {
                    while(i!=beg && nums[i]==nums[i-1]) 
                        continue;               
                    if( i+1 < end+1)
                    {
                        one.add(nums[i]);
                        kSumByDG(kSum-1, nums, i+1, end+1, target, one);
                        one.remove(one.size()-1);
                    }
                }
            }
        }
    
        /*
         * 通过循环，来实现，和上面通过递归实现的本质是一样的。
         * */
        public List<List<Integer>> fourSum(int[] nums, int target)
        {
            List<List<Integer>> finResList=new ArrayList<>();
            if(nums==null ||nums.length<4)
                return finResList;      
            Arrays.sort(nums);
            for(int i=0;i<nums.length-3;i++)
            {
                if(i>0 && nums[i]==nums[i-1]) continue;
                for(int j=i+1;j<nums.length-2;j++)
                {
                    if(j!=i+1 && nums[j]==nums[j-1]) continue;
                    int beg=j+1;
                    int end=nums.length-1;
                    while(beg < end)
                    {
                        int sum = nums[i] + nums[j] + nums[beg] + nums[end];
                        if(sum==target)
                        {
                             List<Integer> t = new ArrayList<Integer>();
                             t.add(nums[i]);
                             t.add(nums[j]);
                             t.add(nums[beg]);
                             t.add(nums[end]);
                             finResList.add(t);
                             while(beg<end && nums[beg+1]==nums[beg])
                                 beg++;
                             while(beg<end && nums[end-1]==nums[end])
                                 end--;
                             beg++;
                             end--;
                        }else if(sum < target)
                            beg++;
                        else 
                            end--;
                    }
                }
            }
            return finResList;
        }
    
        HashMap<Integer, List<List<Integer>>> map=new HashMap<>();
        List<List<Integer>> finResList=new ArrayList<>();
        List<List<Integer>> finIndexList=new ArrayList<>();
    
        //使用hash需靠考虑的细节实在是太多了，下面的方法并不能覆盖所有情况
        public List<List<Integer>> fourSumWithHash(int[] nums, int target)
        {
            Arrays.sort(nums);
            if(nums==null || nums.length<4)
                return finResList;      
            else if(nums.length==4)
            {
                int sum=0;
                List<Integer> tt=new ArrayList<>();
                for(int i=0;i<nums.length;i++)
                {
                    tt.add(nums[i]);
                    sum+=nums[i];
                }
                if(sum==target)
                    finResList.add(tt);
                return finResList;
            }
    
            for(int i=0;i<nums.length;i++)
            {
                for (int j = i+1; j < nums.length; j++) 
                {
                    int sum=nums[i] + nums[j];
                    List<Integer> tmp=new ArrayList<>();
                    tmp.add(i);
                    tmp.add(j);
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    List<List<Integer>> res=map.get(sum);
                    if(res==null)
                    {
                        res=new ArrayList<>();
                        map.put(sum, res);
                    }
                    map.get(sum).add(tmp);
                }
            }
    
            List<Integer> key=new ArrayList<>(map.keySet());
            key.sort(null); 
            int left=0,right=key.size()-1;
            while(left <= right)
            {
                int sum=key.get(left) + key.get(right);
                if(sum==target)
                {
                    List<List<Integer>> res1=map.get(key.get(left));
                    List<List<Integer>> res2=map.get(key.get(right));
                    for (int j = 0; j < res1.size(); j++) 
                    {
                        for (int k = 0; k < res2.size(); k++)
                        {
                            AddOne(res1.get(j),res2.get(k));
                        }
                    }
                    left++;
                    right--;
    
                }else if(sum < target)
                    left++;
                else
                    right--;
            }
            return finResList;
    
        }
    
        public void AddOne(List<Integer> a,List<Integer> b)
        {
            Set<Integer> set=new HashSet<Integer>();
            set.add(a.get(0));
            set.add(a.get(1));
            set.add(b.get(0));
            set.add(b.get(1));
            if(set.size()<4)
                return ;
    
            List<Integer> index=new ArrayList<>(set);
            index.sort(null);
            boolean need=true;
    
            /*
             * 重复添加问题的解决，先判断index的重复
             * */
            for(int i=0;i<finIndexList.size();i++)
            {
                List<Integer> tt=finIndexList.get(i);
                if(tt.get(0)==index.get(0) && tt.get(1)==index.get(1) && tt.get(2)==index.get(2) && tt.get(3)==index.get(3))
                {
                    need=false;
                    break;
                }
            }
            if(need)
            {
                List<Integer> res=new ArrayList<>();
                res.add(a.get(2));
                res.add(a.get(3));
                res.add(b.get(2));
                res.add(b.get(3));
                res.sort(null);
                boolean sub=true;
    
                //index不重复的前提下考虑，具体数值的重复
                for(int i=0;i<finResList.size();i++)
                {
                    List<Integer> tt=finResList.get(i);
                    if(tt.get(0)==res.get(0) && tt.get(1)==res.get(1) && tt.get(2)==res.get(2) && tt.get(3)==res.get(3))
                    {
                        sub=false;
                        break;
                    }
                }
                if(sub)
                    finResList.add(res);    
            }
        }
    
    
        public static void main(String[] args) 
        {
            Solution so=new Solution();
            int []nums={-2,-1,0,0,1,2};
            System.out.println(so.fourSum(nums, 0));
        }
    }

下面是KSum的C++实现，主要是通过把K Sum 降低为k-1 Sum来做的，就是一个递归解决问题。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> fourSum(vector<int>& nums, int target) 
        {
            sort(nums.begin(), nums.end());
            calaKSum(nums, target, 4);
            return res;
        }
    
        void calaKSum(vector<int>& a, int tar,int k)
        {
            vector<int> one;
            dfs(a, tar, k, one, 0, a.size() - k + 1);
        }
    
        void dfs(vector<int>& a, int tar, int k, vector<int>& one, int beg, int end)
        {
            if (k == 2)
            {
                int sum = accumulate(one.begin(), one.end(), 0);
                int left = beg, right = end;
                while (left < right)
                {
                    int tmp = sum + a[left] + a[right];
                    if (tmp == tar)
                    {
                        vector<int> tmp = one;
                        tmp.push_back(a[left]);
                        tmp.push_back(a[right]);
                        res.push_back(tmp);
                        while (left < right && a[left] == a[left + 1]) left++;
                        while (left < right && a[right] == a[right - 1]) right--;
                        left++;
                        right--;
                    }
                    else if (tmp < tar)
                        left++;
                    else
                        right--;
                }
            }
            else
            {
                for (int i = beg; i < end; i++)
                {
                    if (i != beg && a[i] == a[i - 1])
                        continue;
                    one.push_back(a[i]);
                    dfs(a, tar, k-1, one, i + 1, end+1);
                    one.pop_back();
                }
            }
        }
    };

[leetcode 454. 4Sum II]: http://blog.csdn.net/JackZhang_123/article/details/78760370

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 18. 4Sum

iven an array nums of n integers and an integer target, are there elements a, b, c, a...

亦凉/ 2024年04月17日 20:35/ 0 赞/ 63 阅读

相关 LeetCode - Medium - 18. 4Sum

Topic Array Hash Table Two Pointers Description [https://leetcode.com/pr

àì夳堔傛蜴生んèń/ 2023年01月01日 13:50/ 0 赞/ 103 阅读

相关 18 4Sum

类似的题目有 [1 TwoSum][] [15 3Sum][] [16 3Sum Closest][] 第一次使用的是笨办法，四层嵌套for循环，总是超时

痛定思痛。/ 2022年08月10日 00:50/ 0 赞/ 130 阅读

相关 leetcode 18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b +

浅浅的花香味﹌/ 2022年07月29日 08:40/ 0 赞/ 143 阅读

相关 Leetcode——18.4Sum

1. 概述 1.1 题目 Given an array S of n integers, are there elements a, b, c, and d in

「爱情、让人受尽委屈。」/ 2022年06月14日 09:24/ 0 赞/ 119 阅读

相关 [Leetcode][求和问题2Sum/3Sum/4Sum/KSum]相关题目汇总/分析/总结

以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。目前范围：Leetcode前150题 K-SUM解题思路本总结参考：[博客][Link 1]，[S

川长思鸟来/ 2022年06月10日 06:23/ 0 赞/ 156 阅读

相关 leetcode 18. 4Sum KSum的解决办法

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b +

向右看齐/ 2022年06月09日 07:55/ 0 赞/ 138 阅读

相关 Leetcode 18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b +

待我称王封你为后i/ 2022年06月02日 07:48/ 0 赞/ 156 阅读

相关【LeetCode.18】4Sum （C++、Python3）

问题描述 > Given an array nums of n integers and an integer target, are there elements a,

淡淡的烟草味﹌/ 2022年04月25日 05:12/ 0 赞/ 155 阅读

相关 18.4sum

Given an array `nums` of n integers and an integer `target`, are there elements a, b, c,

Myth丶恋晨/ 2021年11月16日 11:58/ 0 赞/ 222 阅读