Related Topics:[Array][Hash Table][Two Pointers]
Similar Questions:[Two Sum][3Sum][4Sum II]
题目: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]
]
LeetCode中关于数字之和还有其他几道,分别是[Two Sum 两数之和],[3Sum 三数之和],[3Sum Closest 最近三数之和],虽然难度在递增,但是整体的套路都是一样的,此题的O(n^3)解法的思路跟[3Sum 三数之和]基本没啥区别,就是多加了一层for循环,其他的都一样。
java解法:
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res=new LinkedList<>();
Arrays.sort(nums);
int i=0;
while(i<nums.length-3) {
//当与前一个元素相同时,跳过该元素的检查。
if(i==0||(i!=0&&(nums[i]!=nums[i-1]))) {
int j=i+1;
while(j<nums.length-2) {
if(j==i+1||(j!=i+1&&(nums[j]!=nums[j-1]))){
int lo=j+1;
int hi=nums.length-1;
int sum=target-nums[i]-nums[j];
while(lo<hi){
if(nums[lo]+nums[hi]==sum) {
res.add(Arrays.asList(nums[i],nums[j],nums[lo],nums[hi]));
lo++;hi--;
//如果该元素与前(后)一元素相同,则跳过元素
while(lo<hi&&nums[lo]==nums[lo-1]) lo++;
while(lo<hi&&nums[hi]==nums[hi+1]) hi--;
}else if(nums[lo]+nums[hi]<sum) {
lo++;
}else hi--;
}
}
j++;
}
}
i++;
}
return res;
}
}