P53 相加等于 0 的三个数

描述#

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

比如说，给你的数组是：
-1, 0, -1, 0, 1, 0, -4
这个数组中有两个组合，使得三个数相加等于 0。第一个组合是：
-1, 0, 1
虽然数组里有 3 个 0，两个 -1，但不管用哪个 0 或 -1，组合 -1,0,1 都只算一个。另一个有效的组合是：
0, 0, 0

代码#

public class AlgoCasts {

  // Time: O(n^3), Space: O(n)
  public List<List<Integer>> threeNumSumToZeroOn3(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length; ++i)
      for (int j = i+1; j < nums.length; ++j)
        for (int k = j+1; k < nums.length; ++k)
          if (nums[i] + nums[j] + nums[k] == 0) {
            List<Integer> elem = Arrays.asList(nums[i], nums[j], nums[k]);
            if (set.contains(elem)) continue;
            set.add(elem);
            result.add(elem);
          }

    return result;
  }

  // Time: O(n^2), Space: O(1)
  public List<List<Integer>> threeNumSumToZeroOn2(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);

    for (int k = nums.length-1; k >= 2; --k) {
      if (nums[k] < 0) break;
      int target = -nums[k], i = 0, j = k-1;
      while (i < j) {
        if (nums[i] + nums[j] == target) {
          result.add(Arrays.asList(nums[i], nums[j], nums[k]));
          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] < target) {
          ++i;
        } else {
          --j;
        }
      }
      while (k >= 2 && nums[k-1] == nums[k]) --k;
    }

    return result;
  }

}