转载

LeetCode题解:15. 三数之和,JavaScript双循环+HashMap,详细注释

原题链接: leetcode-cn.com/problems/3s…

实现思路

  1. 第一层循环用于生成target,相当于 两数之和 中的target。
  2. 第二层循环套用 两数字和 的一遍哈希表解法。
  3. 该题需要去重,这点要特别注意。
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let result = [];
  // 先排序,防止顺序错误的失败
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 1; i++) {
    // 当前值大于0时,3个数都大于0,3数之和必然大于0,无需判断
    if (nums[i] > 0) {
      break;
    }
    // 如果当前值与前一个值相等,即为已经处理过
    // 而且由于是向前比较,因此不会出现遗漏,因为数组的遍历是向后的
    if (nums[i - 1] === nums[i]) {
      continue;
    }
    // target等同于tow-sum中的target
    const target = 0 - nums[i];
    let map = new Map();

    for (let j = i + 1; j < nums.length; j++) {
      // 与tow-sum不同,tow-sum不考虑可能出现相同解的情况,而该题需要考虑
      // 由于nums[i]已经做过去重判断,此处只要判断结果的后两个值没有出现过即可
      // 而由于nums已经排序过,只要对比上一个结果即可
      if (result.length) {
        if (
          result[result.length - 1][1] === target - nums[j] &&
          result[result.length - 1][2] === nums[j]
        ) {
          continue;
        }
      }

      // tow-sum的判断方式,使用map进行判断
      // 如果当前值已存在map中,则为当前结果。
      if (typeof map.get(nums[j]) === 'number') {
        result.push([nums[i], map.get(nums[j]), nums[j]]);
      }
      // 每次循环都缓存一次当前值,key为target - nums[j]
      // 如果下次循环到的值与key相同,则可以直接取出之前的nums[j]
      map.set(target - nums[j], nums[j]);
    }
  }

  return result;
};
复制代码
原文  https://juejin.im/post/5f0db691518825742109d967
正文到此结束
Loading...