P165 相加等于目标值的四个数

描述#

这个题目说的是，给你一个整数数组和一个目标值，你要找到数组中四个数相加等于目标值的所有可能组合。返回的答案里，每个组合都是唯一的，不能重复。

比如说，给你的数组是：
[1, 0, -1, 0, -3, 2]
给你的目标值是 0。
这个数组中有两个组合，使得 4 个数相加等于目标值 0。第一个组合是：
[-3, 0, 1, 2]
虽然数组中有两个 0，但是不管使用哪个 0，组合 [-3, 0, 1, 2] 都只算作一个。
另一个相加等于目标值的组合是：
[-1, 0, 0, 1]

代码#

public class AlgoCasts {

  // Time: O(n^3), Space: O(1)
  public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 4) return result;
    Arrays.sort(nums);

    for (int p = nums.length-1; p >= 3; --p) {
      if (4*nums[p] < target) break;
      for (int k = p-1; k >= 2; --k) {
        if (3*nums[k]+nums[p] < target) break;
        int newTarget = target - nums[k] - nums[p];
        int i = 0, j = k-1;
        while (i < j) {
          if (nums[i] + nums[j] == newTarget) {
            result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[p]));
            while (i < j && nums[i+1] == nums[i]) ++i;
            while (i < j && nums[j-1] == nums[j]) --j;
            ++i; --j;
          } else if (nums[i] + nums[j] < newTarget) {
            ++i;
          } else {
            --j;
          }
        }
        while (k >= 2 && nums[k-1] == nums[k]) --k;
      }
      while (p >= 3 && nums[p-1] == nums[p]) --p;
    }
    return result;
  }

}