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

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » LeetCode题解:15. 三数之和,JavaScript双循环+HashMap,详细注释

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址