二刷。
还是部分遍历＋滑窗。
难点在于如何跳过重复的元素。
滑窗过程中遇到重复元素，和前2个固定坐标遇到重复元素是不一样的。
So u shall handle them in different ways respectively.滑窗过程中，一旦判定成功，左右坐标的下一个如果相同，都没有判断的必要，所以要往二者之间不停地滑。“小心地滑”(beware of the slippery floor) 标识牌翻译成 slide cautiously
固定坐标遇到和上一个相等也要滑。。
public class Solution { public List > fourSum(int[] nums, int target) { List > res = new ArrayList >(); if(nums.length < 4) return res; Arrays.sort(nums); for(int i = 0; i < nums.length-3;i++) { for(int j = i+1; j < nums.length-2;j++) { int L = j+1; int R = nums.length-1; int total = nums[i] + nums[j]; while(L < R) { if(total + nums[L] + nums[R] > target) R--; else if(total + nums[L] + nums[R] < target) L++; else { List tempList = new ArrayList<>(); tempList.add(nums[i]);tempList.add(nums[j]);tempList.add(nums[L]);tempList.add(nums[R]); res.add(new ArrayList<>(tempList)); while(L < R && nums[L] == nums[L+1]) L++; while(L < R && nums[R] == nums[R-1]) R--; R--;L++; } } while(j < nums.length-2 && nums[j] == nums[j+1]) j++; } while(i < nums.length -1 && nums[i] == nums[i+1]) i++; } return res; }}
二刷。
固定2个，然后夹逼。
注意去重，然后别忘了一开始排序。。。
Time: O(nlgn)排序 + O(n³)
Space: O(n)public class Solution { public List > fourSum(int[] nums, int target) { List > res = new ArrayList<>(); if (nums.length < 4) return res; Arrays.sort(nums); for (int i = 0; i < nums.length - 3; i++) { for (int j = i + 1; j < nums.length - 2; j++) { int left = target - nums[i] - nums[j]; int l = j + 1; int r = nums.length - 1; while (l < r) { if (nums[l] + nums[r] < left) { l ++; } else if (nums[l] + nums[r] > left) { r --; } else { List tempList = new ArrayList<>(); tempList.add(nums[i]); tempList.add(nums[j]); tempList.add(nums[l ++]); tempList.add(nums[r --]); res.add(tempList); while (l < r && nums[l] == nums[l-1]) { l ++; } while (l < r && nums[r] == nums[r+1]) { r --; } } } while (j < nums.length - 1 && nums[j] == nums[j+1]) { j ++; } } while (i < nums.length - 1 && nums[i] == nums[i+1]) { i ++; } } return res; }}