No.018：4Sum-白红宇的个人博客

No.018：4Sum

发布日期：2021-05-09 03:58:59 浏览次数：18 分类：博客文章

本文共 2791 字，大约阅读时间需要 9 分钟。

问题：

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]

]

官方难度：

Medium

翻译：

给定一个长度为n的无序数组S和目标数字target，在数组S中找出4个整数a,b,c,d，使a+b+c+d=target。

找出所有的可能解，且解集中不包含重复项。

例子：

数组S:{ 1, 0, -1, 0, -2, 2}，目标值target=0。

解集为[ [-1,0,0,1],[-2,-1,1,2],[-2,0,0,2] ]。

显然，本题是No.001（Two Sum），No.015（3Sum），No.016（3Sum Closest）更深一步的讨论。在解决这道问题时，不妨考虑一种解法，适用于5Sum，6Sum之后一系列的问题。我可以将这些问题总结归纳为：kSum问题，k>=2。

显然是需要使用递归，而递归的终点就是2Sum问题。

将递归方法独立出来，在进入递归之前，优先给数组排序（如k=2，这种做法会略微影响性能）。

2Sum问题，仍然使用夹逼的原则，同时维护两侧的previous值。增加优化策略：当前左值大于目标数且当前左值大于0，return；当2倍前左值大于目标值，或2倍当前右值小于目标值，return。

当k>2时，做类似2Sum的优化策略，将当前目标值-当前值，作为递归入参的目标值，同时传入当前索引值，进行递归。

获得递归的解集，循环加入当前值到解集中返回。

注意入参检查。

解题代码：

1     public static List
     
      
       > fourSum(int[] nums, int target) { 2         if (nums == null || nums.length < 4) { 3             throw new IllegalArgumentException("Input error"); 4         } 5         Arrays.sort(nums); 6         return kSum(nums, 0, target, 4); 7     } 8  9     private static List
       
        
         > kSum(int[] nums, int startIndex, int target, int kSum) {10         List
         
          
           > result = new LinkedList<>();11 // 递归终点是2Sum问题12 if (kSum == 2) {13 int left = startIndex, right = nums.length - 1;14 int preLeft = Integer.MIN_VALUE, preRight = Integer.MIN_VALUE;15 while (left < right) {16 if (nums[left] > target && nums[left] > 0) {17 return result;18 }19 if (2 * nums[left] > target || 2 * nums[right] < target) {20 return result;21 }22 if (nums[left] == preLeft) {23 left++;24 continue;25 }26 if (nums[right] == preRight) {27 right--;28 continue;29 }30 int sum = nums[left] + nums[right];31 if (sum == target) {32 List
           
             list = new LinkedList<>();33 list.add(nums[left]);34 list.add(nums[right]);35 result.add(list);36 }37 if (sum < target) {38 preLeft = nums[left];39 left++;40 } else {41 preRight = nums[right];42 right--;43 }44 }45 } else {46 // 大于2Sum问题，使用递归47 int previous = Integer.MAX_VALUE;48 for (int i = startIndex; i < nums.length - 1; i++) {49 if (nums[i] > target && nums[i] > 0) {50 return result;51 }52 // target值的范围超过k个极值53 if (kSum * nums[i] > target || kSum * nums[nums.length - 1] < target) {54 return result;55 }56 if (nums[i] == previous) {57 continue;58 }59 int tempTarget = target - nums[i];60 // 开启递归61 List
            
             
              > tempResult = kSum(nums, i + 1, tempTarget, kSum - 1);62 for (List
              
                a : tempResult) {63 a.add(nums[i]);64 result.add(a);65 }66 previous = nums[i];67 }68 }69 return result;70 }

fourSum

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章