前端刷题路-Day8|刷题打卡

我心飞翔 分类:javascript

掘金团队号上线,助你 Offer 临门! 点击 查看详情

三数之和(题号15)

题目

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 abc ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
 

示例 2:

输入:nums = []
输出:[]
 

示例 3:

输入:nums = [0]
输出:[]
 

提示:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

链接

leetcode-cn.com/problems/3s…

解释

这题说实话,自己想了半天也没想出来,只想到了最暴力的一种解法,更好的答案完全没有想法,后来看了课才勉勉强强了解了左右指针的解法,这种问题感觉只有看过才会解答啊,否则正常情况下谁没事会想到这种解决方案。

解决方法也很简单:首先将数组进行排序,从小到大和从大到小都是可以的,就是后面的操作会有些许不同,但是问题不大,这里是从小到大排序。

老规矩,先是判断数据是否是正常的数据,如果不是直接返回空数组

之后循环数组,首先,如果循环到的数字大于0,那么意味着后续永远不会有想匹配的两个数字相加为0,因为数组是从小到大排列的,后面的数只会和0相等或者大于0

之后如果当前的i和下一个i的值是一样的,那么跳过这次循环,为了去重

之后就是拿到i后面的左指针L和右指针R,这块就没啥可说的了,就一直挪动指针呗,直到找到合适的值为止,如果没有就进入到下一次循环当中

自己的答案

更好的解答

var threeSum = function(nums) {
  // 数组长度不满足条件直接返回
  if (!nums || nums.length < 3) return []
  // 数组排序
  nums.sort((a, b) => a- b)
  // 最后的结果放这里
  var res = []
      len = nums.length
  // 开始循环
  for (let i = 0; i < len; i++) {
    // 如果当前元素大于0,证明后续元素的和永远不可能为0,直接返回
    if (nums[i] > 0) break
    // 如果当前元素和上一位元素相同,跳过这次循环
    if (i > 0 && nums[i] === nums[i - 1]) continue
    // 定义左右指针
    var L = i + 1
        R = len - 1
    // 开始移动指针
    while (L < R) {
      var sum = nums[i] + nums[L] + nums[R]
      if (sum === 0) {
        // 如果和为0,满足条件,添加进结果数组
        res.push([nums[i], nums[L], nums[R]])
        // 如果左右指针和前后的值相同,跳过该值
        while (nums[R] === nums[R - 1]) R--
        while (nums[L] === nums[L + 1]) L++
        // 正常移动左右指针
        L++
        R--
      } else if (sum > 0) {
        // 值太大移动右指针
        R--
      } else {
        // 值太小移动左指针
        L++
      }
    }
  }
  return res
};
 

PS:想查看往期文章和题目可以点击下面的链接:

这里是按照日期分类的👇

前端刷题路-目录(日期分类)

经过有些朋友的提醒,感觉也应该按照题型分类
这里是按照题型分类的👇

前端刷题路-目录(题型分类)

有兴趣的也可以看看我的个人主页👇

Here is RZ

回复

我来回复
  • 暂无回复内容