题目

思路

整体在三数之和的基础上进行修改。（所有需要修改的地方，我在代码里加了//改 的注释）

大的一个思路就是，在三数之和的外面再套一层循环。相当于固定前两个数。然后这道题目标值变成一个参数了，不是三数之和的0了。所以我们把a+b+c+d=target的放到res列表里。注意这里求sum 用了long，因为测试案例中有一些数非常大。

需要注意的细节就是a,b,c,d的去重。

a的去重和我们三数之和a的去重一样。j>0 && nums[j] == nums[j - 1]。

b的去重我们修改成了i>j+1 && nums[i] == nums[i - 1]。为啥写成这，而不是i>1呢？看个例子 [-2，-1，-1，1，1，2，2] target=0。如果i>1 就剪枝的话，当j=1,i=2的时候 这时候nums[2]==nums[3]直接就被剪掉了，而我们还没有搜索呢。

c的去重很简单，就是把原来sum>0,改成了sum>target。

d的去重类推。

此外还有一个细节就是，不要判断a > target 就break，因为这次我们的target可能是负数，这和三数之和不一样了。

举个例子：[-4,-3,-2,-1],target=-10。虽然a>target，但是仍然有sum能等于target。如果我们的数组所有的数都是正数，就可以按原来的剪枝。

代码

import java.sql.Array;
import java.util.ArrayList;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<>();//对数组从小到大进行排序Arrays.sort(nums);for (int j = 0; j < nums.length; j++) {if (nums[j] > 0 && nums[j] > target) //改break;//对a去重if (j > 0 && nums[j] == nums[j - 1]) {continue;}for (int i = j + 1; i < nums.length; i++) {  //改//对b去重if (i > j + 1 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (right > left) {long sum = (long) nums[j] + nums[i] + nums[left] + nums[right]; //改if (sum > target) {  //改right--;} else if (sum < target) { //改left++;} else {res.add(Arrays.asList(nums[j], nums[i], nums[left], nums[right]));  //改//对c和d去重while (right > left && nums[left] == nums[left + 1]) left++;while (right > left && nums[right] == nums[right - 1]) right--;//找到一个四元组后，继续寻找下一个四元组left++;right--;}}}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)