15. 3Sum

source: https://leetcode.com/problems/3sum/

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

暴力法

这道题可以粗暴的用三个loop去比较，然后筛选distinct的tuple. 很明显，时间复杂度是O(n3), 在leetcode上是会超标的。

var threeSum = function (nums) {
  const ret = [];
  for (let i1 = 0; i1 < nums.length; i1++) {
    for (let i2 = 0; i2 < nums.length; i2++) {
      if (i1 === i2) continue;
      for (let i3 = 0; i3 < nums.length; i3++) {
        if (i2 === i3 || i1 === i3) continue;
        const a = nums[i1];
        const b = nums[i2];
        const c = nums[i3];
        if (a + b + c === 0) {
          const v = [a, b, c].sort((a, b) => a - b).join(",");
          if (!ret.includes(v)) ret.push(v);
        }
      }
    }
  }
  return ret.map((v) => v.split(","));
};

优化思路

由于三个元素是不重复的，可以得到一个不等式：

• a <= b <= c

且有多个loop, 很容易想到用左右指针的思路去做优化。

var threeSum = function (nums) {
  const ret = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    let p1 = i + 1;
    let p2 = nums.length - 1;
    while (p1 < p2) {
      const v = nums[i] + nums[p1] + nums[p2];
      if (v > 0) {
        p2--;
      } else if (v < 0) {
        p1++;
      } else {
        const s = `${[nums[i], nums[p1], nums[p2]]}`;
        if (!ret.includes(s)) ret.push(s);
        p1++;
        p2--;
      }
    }
  }
  return ret.map((v) => v.split(","));
};

优化不判断重复值：

var threeSum = function (nums) {
  const ret = [];
  nums.sort((a, b) => a - b);
  for (let i1 = 0; i1 < nums.length; i1++) {
    const a = nums[i1];
    if (a > 0) return ret;
    if (i1 > 0 && a === nums[i1 - 1]) continue;
    let p1 = i1 + 1;
    let p2 = nums.length - 1;
    while (p1 < p2) {
      const v = a + nums[p1] + nums[p2];
      if (v > 0) {
        p2 -= 1;
      } else if (v < 0) {
        p1 += 1;
      } else {
        ret.push([a, nums[p1], nums[p2]]);
        while (p1 < p2 && nums[p1] === nums[p1 + 1]) p1 += 1;
        while (p1 < p2 && nums[p2] === nums[p2 - 1]) p2 -= 1;
        p1 += 1;
        p2 -= 1;
      }
    }
  }
  return ret;
};

总结

对于排序数组，多个loop，可以忘双指针这个思路去优化。