给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
提示：
0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码实现：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums == null || nums.length < 4) {
return new ArrayList<>();
}
Arrays.sort(nums);
int len = nums.length;
List<List<Integer>> result = new ArrayList<>();
for (int i = len-1; i >= 3; i--) {
if (nums[i] + nums[i - 1] + nums[i - 2] + nums[i - 3] <target) {
break;
}
for (int j = i - 1; j >= 2; j--) {
if (nums[i] + nums[j - 1] + nums[j - 2] + nums[j] <target) {
break;
}
for (int k = j - 1; k >= 1; k--) {
if (nums[i] + nums[k - 1] + nums[k] + nums[j] <target) {
break;
}
for (int l = k - 1; l >= 0; l--) {
if (nums[i] + nums[l] + nums[k] + nums[j] <target) {
break;
}
if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
List<Integer> ll = new ArrayList<>();
ll.add(nums[i]);
ll.add(nums[j]);
ll.add(nums[k]);
ll.add(nums[l]);
Collections.sort(ll);
if (!result.contains(ll)) {
result.add(ll);
}
}
}
}
}
}
return result;
}
}
