|
| 1 | +#[4Sum][title] |
| 2 | + |
| 3 | +##Description |
| 4 | + |
| 5 | +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. |
| 6 | + |
| 7 | +**Note:** The solution set must not contain duplicate quadruplets. |
| 8 | + |
| 9 | +``` |
| 10 | +For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. |
| 11 | +
|
| 12 | +A solution set is: |
| 13 | +[ |
| 14 | + [-1, 0, 0, 1], |
| 15 | + [-2, -1, 1, 2], |
| 16 | + [-2, 0, 0, 2] |
| 17 | +] |
| 18 | +``` |
| 19 | + |
| 20 | +**Tags:** Array, Hash Table, Two Pointers |
| 21 | + |
| 22 | + |
| 23 | +##思路 0 |
| 24 | + |
| 25 | +这道题和[3Sum][015] 的思路基本一样，先对数组进行排序，然后遍历这个排序数组，因为这次是四个元素的和，所以外层需要两重循环，然后还是用两个指针分别指向当前元素的下一个和数组尾部，判断四者的和与`target` 的大小来移动两个指针，其中细节操作还是优化和去重。 |
| 26 | + |
| 27 | +```java |
| 28 | +classSolution { |
| 29 | +publicList<List<Integer>>fourSum(int[]nums,inttarget) { |
| 30 | +List<List<Integer>> res=newArrayList<>(); |
| 31 | +int len= nums.length; |
| 32 | +if (len<4)return res; |
| 33 | +Arrays.sort(nums); |
| 34 | +int max= nums[len-1]; |
| 35 | +if (4* max< target)return res; |
| 36 | +for (int i=0; i< len-3;) { |
| 37 | +if (nums[i]*4> target)break; |
| 38 | +if (nums[i]+3* max< target) { |
| 39 | +while (nums[i]== nums[++i]&& i< len-3) ; |
| 40 | +continue; |
| 41 | + } |
| 42 | + |
| 43 | +for (int j= i+1; j< len-2;) { |
| 44 | +int subSum= nums[i]+ nums[j]; |
| 45 | +if (nums[i]+ nums[j]*3> target)break; |
| 46 | +if (subSum+2* max< target) { |
| 47 | +while (nums[j]== nums[++j]&& j< len-2) ; |
| 48 | +continue; |
| 49 | + } |
| 50 | + |
| 51 | +int left= j+1, right= len-1; |
| 52 | +while (left< right) { |
| 53 | +int sum= subSum+ nums[left]+ nums[right]; |
| 54 | +if (sum== target) { |
| 55 | + res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); |
| 56 | +while (nums[left]== nums[++left]&& left< right); |
| 57 | +while (nums[right]== nums[--right]&& left< right); |
| 58 | + }elseif (sum< target)++left; |
| 59 | +else--right; |
| 60 | + } |
| 61 | +while (nums[j]== nums[++j]&& j< len-2) ; |
| 62 | + } |
| 63 | +while (nums[i]== nums[++i]&& i< len-3) ; |
| 64 | + } |
| 65 | +return res; |
| 66 | + } |
| 67 | +} |
| 68 | +``` |
| 69 | + |
| 70 | + |
| 71 | +##思路 1 |
| 72 | + |
| 73 | +从[Two Sum][001]、[3Sum][015] 到现在的 4Sum，其实都是把高阶降为低阶，那么我们就可以写出 kSum 的函数来对其进行降阶处理，降到 2Sum 后那么我们就可以对其进行最后的判断了，代码如下所示，也终也做了相应的优化和去重。 |
| 74 | + |
| 75 | +```java |
| 76 | +classSolution { |
| 77 | +publicList<List<Integer>>fourSum(int[]nums,inttarget) { |
| 78 | +Arrays.sort(nums); |
| 79 | +int len= nums.length; |
| 80 | +if (len<4)returnCollections.emptyList(); |
| 81 | +int max= nums[len-1]; |
| 82 | +if (4* max< target)returnCollections.emptyList(); |
| 83 | +return kSum(nums,0,4, target); |
| 84 | + } |
| 85 | + |
| 86 | +privateList<List<Integer>>kSum(int[]nums,intstart,intk,inttarget) { |
| 87 | +List<List<Integer>> res=newArrayList<>(); |
| 88 | +if (k==2) { |
| 89 | +int left= start, right= nums.length-1; |
| 90 | +while (left< right) { |
| 91 | +int sum= nums[left]+ nums[right]; |
| 92 | +if (sum== target) { |
| 93 | +List<Integer> twoSum=newLinkedList<>(); |
| 94 | + twoSum.add(nums[left]); |
| 95 | + twoSum.add(nums[right]); |
| 96 | + res.add(twoSum); |
| 97 | +while (nums[left]== nums[++left]&& left< right) ; |
| 98 | +while (nums[right]== nums[--right]&& left< right) ; |
| 99 | + }elseif (sum< target)++left; |
| 100 | +else--right; |
| 101 | + } |
| 102 | + }else { |
| 103 | +int i= start, end= nums.length- (k-1), max= nums[nums.length-1]; |
| 104 | +while (i< end) { |
| 105 | +if (nums[i]* k> target)return res; |
| 106 | +if (nums[i]+ (k-1)* max< target) { |
| 107 | +while (nums[i]== nums[++i]&& i< end) ; |
| 108 | +continue; |
| 109 | + } |
| 110 | +List<List<Integer>> temp= kSum(nums, i+1, k-1, target- nums[i]); |
| 111 | +for (List<Integer> t: temp) { |
| 112 | + t.add(0, nums[i]); |
| 113 | + } |
| 114 | + res.addAll(temp); |
| 115 | +while (nums[i]== nums[++i]&& i< end) ; |
| 116 | + } |
| 117 | + } |
| 118 | +return res; |
| 119 | + } |
| 120 | +} |
| 121 | +``` |
| 122 | + |
| 123 | + |
| 124 | + |
| 125 | +##结语 |
| 126 | + |
| 127 | +如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl] |
| 128 | + |
| 129 | + |
| 130 | + |
| 131 | +[001]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/001/README.md |
| 132 | +[015]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/015/README.md |
| 133 | +[title]:https://leetcode.com/problems/4sum |
| 134 | +[ajl]:https://github.com/Blankj/awesome-java-leetcode |