题目等级：4Sum（Medium）
题目描述：
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.
Example:
Given array nums = [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]
]
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
解题思路：
这个就没什么特别的了，直接参考三数之和：【LeetCode】15、三数之和为0
网上也没有找到什么其他特别的解法，有说采用二分的方法转化为两个两数之和的，但是感觉过于繁琐了，不太直观，这里就直接采用在三数之和的外层又加了一层循环，时间复杂度为：O(n^3).
然后主要对这类题做一个总结：
两数之和系列，做法：
- 若数组无序，采用HashMap，参考：【LeetCode】1、两数之和
- 若数组有序，双指针，参考：【剑指Offer】42、和为S的两个数字
三数之和（N数之和）序列，做法:
- 第一步：java.util.Arrays.sort(int[] nums)，升序排列
- 第二步：N-2层for循环，外加两个双向指针，双向指针后需while循环向数组中间靠拢，while循环里嵌套两层while循环，用于去重
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res=new ArrayList<>();
if(nums==null && nums.length==0)
return res;
Arrays.sort(nums);
int len=nums.length;
for(int i=0;i<len-3;i++){
if(i>0 && nums[i-1]==nums[i]) //跳过重复的
continue;
for(int j=i+1;j<len-2;j++){
if(j>i+1 && nums[j]==nums[j-1]) //跳过重复的
continue;
int low=j+1,high=len-1,sum=target-nums[i]-nums[j];
while(low<high){
if(nums[low]+nums[high]==sum){ //找到一个解
res.add(Arrays.asList(nums[i],nums[j],nums[low],nums[high]));
while(low<high && nums[low+1]==nums[low])
low++;
while(low<high && nums[high-1]==nums[high])
high--;
low++;
high--;
}else if(nums[low]+nums[high]<sum)
low++;
else
high--;
}
}
}
return res;
}
}