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中關(guān)于數(shù)字之和還有其他幾道，分別是[Two Sum 兩數(shù)之和]猪腕，[3Sum 三數(shù)之和]钦勘，[3Sum Closest 最近三數(shù)之和]，雖然難度在遞增腐缤，但是整體的套路都是一樣的捌归，此題的O(n^3)解法的思路跟[3Sum 三數(shù)之和]基本沒啥區(qū)別惜索，就是多加了一層for循環(huán)剃浇，其他的都一樣。
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) {
//當(dāng)與前一個元素相同時虎囚，跳過該元素的檢查。
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;
}
}
