前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode:15 三数之和

leetcode:15 三数之和

作者头像
贵哥的编程之路
发布2020-10-28 15:23:22
2980
发布2020-10-28 15:23:22
举报
文章被收录于专栏:用户7873631的专栏
代码语言:javascript
复制
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b) // 排序
  let res = []
  for (let i = 0, len = nums.length; i < len; i++) {
    if (nums[i] > 0) break  // 排除不可能情况
    if (i>0 && nums[i] === nums[i - 1]) continue // 去重
    let L = i + 1, R = len -1;
    while (L <R) {
      let sum = nums[i] + nums[L] + nums[R]
      if (sum === 0) {
        res.push([nums[i], nums[L], nums[R]])
        while (nums[L] === nums[++L]) continue // 及时去重
      }else if (sum > 0) {
         
       
        R--;
      }else if (sum < 0) {
    
        
        L++;
      }
    }
  }
  return res
};

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

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

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目解析数组中的某三个数之和必须等于0.,结果可以是多样,不过要保证的是结果中某三个数不能和另外的结果中的某三个数全部重复,位置不同,值相同也不行。(两个三个元素的数组) 思路:先排序好,然后找好一个([0])固定的点,然后左[1]右[length-1]指针遍历就行了。

步骤: 先排序:问题:为什么是nums.sort((a, b) => a - b)这样。而不是nums.sort(a, b)? 因为nums.sort(a, b)这样。默认情况下sort方法是按ascii字母顺序排序的,而非我们认为是按数字大小排序 为什么这种行? 因为这种nums.sort((a, b) => a - b)如果a-b大于0就排序,(因为这是从小到大排序的啊),第一个比第二个大啊,所以。。 如果小于0,就代表第一个比第二个小,因为这种是从小到大排序的哈。 然后是,为什么要排序? 因为排序后才能双指针啊,不然乱乱的,怎么搞?

if (nums[i] > 0) break // 排除不可能情况??? 因为如果第一个大于0,那玩什么啊,全都是大于0的数字怎么等于0啊,兄弟。 if (i>0 && nums[i] === nums[i - 1]) continue // 去重 意思是;如果第二个与第一个相等的话,在i是第二个下标(nums[1])或者以上(nums[自增加1])的情况下,就continue执行for,i=2;。。。 如果还是2与i=1相等,就continue,确保没有重复的值。 执行这句话代表开头的固定的nums[0]与下一个nums[1]不会重复了. 然后是看看双指针里面的重复怎么去掉哈。

代码语言:javascript
复制
 let L = i + 1, R = len - 1;

意思是;因为i等于固定的值,i+1代表做左指针,len-1代表右指针。

代码语言:javascript
复制
 while (L < R) {
      let sum = nums[i] + nums[L] + nums[R]
代码语言:javascript
复制
什么意思?
当L小于R时,为什么时<为什么不是<=呢?
因为等于的话,就错了,为什么,因为给你的数组里面只有一个2,而<=的话,是[-4,2,2]是两个2了。
问题?为什么测试用例里面的-1可以两个啊,因为给的数组里面有两个-1啊。
注意一下:给的数组里面的元素在一个组合;里面只能出现一次。而-1有两个,证明在一个组合里面有两个-1也可以。但是因为2在给的数组里面只有一个,所以一个数组里面只能有一个2,两个2的话,就错了哈。
然后是    `let sum = nums[i] + nums[L] + nums[R]`看看双指针的与固定值的结果能不能为0.
代码语言:javascript
复制
 if (sum === 0) {
        res.push([nums[i], nums[L], nums[R]])
        while (nums[L] === nums[++L]) continue // 及时去重
      }
代码语言:javascript
复制
  意思是;等等于0时,就代表可以,push进输出的数组里面,然后看看这个可以与其他的可以为0的L与下一个L++是不是重复的,
  如果是证明有重复的,就先装进数组里面在跳过下一个,问题?为什么一定要跳过?
  因为不跳过的话,有重复,有重复会错,因为题目要求的是不能重复的:(官方要求)注意:答案中不可以包含重复的三元组。(官方要求)。
 注意下这里:也能重复,不过要求的是给的数组里面的,如果给的数组里面有两个-1,因为每一个-1在一个组合里面只能出现一次,两个2,可以出现两次了啊,就这种情况。
 除了这种,其他的都错。
 问题?为什么使用continue跳过,因为如果break的话,就全部完了啊。(跳过for)。
代码语言:javascript
复制
 else if (sum > 0) {
   R--;
  }

为什么R–因为sum大于0了啊,而右指针是最大的,所以右指针得–啦

代码语言:javascript
复制
else if (sum < 0) {
        L++;
      }

为什么这里L++因为sum小于0了啊,而左指针是最小的,所以左指针得++啦

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/07/29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档