三数之和

问题描述:

给你一个包含 n 个整数的数组  nums，判断  nums  中是否存在三个元素 a，b，c ，使得  a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例:

// Given array nums = [-1, 0, 1, 2, -1, -4],

// A solution set is:
// [
//   [-1, 0, 1],
//   [-1, -1, 2]
// ]

三种解法

解法 1: 暴力的三层循环 超时

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 解法1: 暴力的三层循环 4495501000
var threeSum = function(nums) {
  var result = [];
  var len = nums.length;
  var set = new Set();
  var count = 0;

  for (var i = 0; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      for (var k = j + 1; k < len; k++) {
        count++;
        if (nums[i] + nums[j] + nums[k] === 0) {
          var tmpResult = [nums[i], nums[j], nums[k]];
          var tmpStr = String(tmpResult.sort());
          if (!set.has(tmpStr)) {
            result.push(tmpResult);
            set.add(tmpStr);
          }
        }
      }
    }
  }
  console.log(count);
  return result;
};

testCase1, count : 20 testCase2, count : 4495501000 这种方式， 属于没什么技术含量的， 暴力枚举， 结果当然是超时， 无法通过。 我们可以通过其他的方式来减少循环， 提升性能。

解法 2: O(N^2), 超时

var threeSum = function(nums) {
  let res = [];
  let set = new Set();
  let finalResult = [];
  var l = nums.length;

  if (nums == null || nums.length == 0) {
    return [];
  }
  if (l < 3) return [];
  if (l === 3 && nums[0] + nums[1] + nums[2] === 0) return [nums];

  nums.sort();

  for (var i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    var targetMap = {};

    for (var j = i + 1; j < nums.length; j++) {
      if (targetMap[nums[j]] == 0) {
        res.push([nums[i], nums[j], -(nums[i] + nums[j])]);
        targetMap[nums[j]] = 1;
      } else {
        targetMap[-nums[i] - nums[j]] = 0;
      }
    }
  }

  for (var i = 0; i < res.length; i++) {
    var tmpResult = res[i];
    var tmpStr = String(tmpResult.sort());
    if (!set.has(tmpStr)) {
      finalResult.push(tmpResult);
      set.add(tmpStr);
    }
  }
  return finalResult;
};

解法 3: 双指针

var threeSum = function(nums) {
  var l = nums.length;
  if (l === 3 && nums[0] + nums[1] + nums[2] === 0) return [nums];
  var temp = nums.sort(function(a, b) {
    return a - b;
  });
  var res = [];
  for (var i = 0; i < l; i++) {
    if (i !== 0 && temp[i] === temp[i - 1]) continue;
    var j = i + 1;
    var k = l - 1;
    while (j < k) {
      var sum = temp[i] + temp[j] + temp[k];
      if (sum === 0) {
        res.push([temp[i], temp[j], temp[k]]);
        // break;
        while (j++ < k && temp[j - 1] === temp[j]) {
          /* do nothing*/
        }
        while (k-- > j && temp[k] === temp[k + 1]) {
          /* do nothing*/
        }
      } else if (sum < 0) {
        j++;
      } else {
        k--;
      }
    }
  }
  return res;
};