目 录CONTENT

文章目录

强大的双指针法-leetcode15. 三数之和

Hello!你好!我是村望~!
2022-08-13 / 0 评论 / 0 点赞 / 203 阅读 / 1,320 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

青出于蓝而胜于蓝,三数求和虽然和两数求和只差了一个字,但是思路却完全不同。

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

注意:答案中不可以包含重复的三元组。
 15. 三数之和

双指针法用在涉及求和、比大小类的数组题目里时,大前提往往是:该数组必须有序。否则双指针根本无法帮助我们缩小定位的范围,压根没有意义。因此这道题的第一步是将数组排序:

  1. 先把数组从小到大排序
var threeSum = function (nums: number[]) {
    // 先对数组进行排序!
    nums = nums.sort((a, b) => a - b)
};

threeSum([-1, 0, 1, 2, -1, -4])
[ -4, -1, -1, 0, 1, 2 ]
  1. 然后对数组进行遍历,每次遍历到哪个数字,就固定哪个数字。(注意我们遍历到倒数第三个数就足够了,因为左右指针会遍历后面两个数,所以全部循环次数只有num.length-2
var threeSum = function (nums: number[]) {

    // 先对数组进行排序!
    nums = nums.sort((a, b) => a - b)
    
    //注意我们遍历到倒数第三个数就足够了,因为左右指针会遍历后面两个数,所以全部循环次数只有`num.length-2`)
    for (let i = 0; i < nums.length - 2; i++) {
    
    }
};
  1. 然后把左指针指向该固定数字的后一位!,把右指针指向数组末尾,让左右指针从起点开始,向中间前进
  • 从初始位置开始:小于0,如果当前的小于0,那么就让左指针往右移动,找大一点的!
  • 反之:如果当前的大于0,那么就让右指针往左移动,找小一点的!
 /**
 * @param {number[]} nums
 * @return {number[][]}
 * 
示例 1:
    输入:nums = [-1,0,1,2,-1,-4]
    输出:[[-1,-1,2],[-1,0,1]]
示例 2:
    输入:nums = []
    输出:[]
示例 3:
    输入:nums = [0]
    输出:[]

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 */
var threeSum = function (nums: number[]) {
    let ret: number[][] = []
    // 先对数组进行从小到大排序!
    nums = nums.sort((a, b) => a - b); //[ -4, -1, -1, 0, 1, 2 ]
    //注意我们遍历到倒数第三个数就足够了,因为左右指针会遍历后面两个数,所以全部循环次数只有`num.length-2`)
    for (let i = 0; i < nums.length - 2; i++) {
        let l = i + 1;
        let r = nums.length - 1;
        while (l < r) {
            if (nums[i] + nums[l] + nums[r] < 0) {
                // 因为排序是从小到大的,如果当前的小于0,那么就让左指针往右移动,找大一点的!
                l += 1
            } else if (nums[i] + nums[l] + nums[r] > 0) {
                // 因为排序是从大到小的,如果当前的大于0,那么就让右指针往左移动,找小一点的!
                r -= 1
            } else {
                // 如果找到了,那么就存起来,并且同时向内移动一位继续寻找!
                ret.push([nums[i], nums[l], nums[r]])
                l += 1;
                r -= 1;
            }
        }
    }
    console.log('====================================');
    console.log(ret);
    console.log('====================================');
};
threeSum([-1, 0, 1, 2, -1, -4])

输出结果:

====================================
[ [ -1, -1, 2 ], [ -1, 0, 1 ], [ -1, 0, 1 ] ]
====================================

下面还需要去处理一下重复的情况!

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
   let ret = []
   // 先对数组进行从小到大排序!
   nums = nums.sort((a, b) => a - b); //[ -4, -1, -1, 0, 1, 2 ]
   //注意我们遍历到倒数第三个数就足够了,因为左右指针会遍历后面两个数,所以全部循环次数只有`num.length-2`)
   for (let i = 0; i < nums.length - 2; i++) {
       let l = i + 1;
       let r = nums.length - 1;
       // 固定了重复的值,跳过!
       if (i > 0 && nums[i] === nums[i - 1]) {
           continue
       }
       while (l < r) {
           if (nums[i] + nums[l] + nums[r] < 0) {
               l += 1
               // 因为排序是从小到大的,如果当前的小于0,那么就让左指针往右移动,找大一点的!
               // 如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[l] === nums[l - 1]) {
                   l += 1
               }
           } else if (nums[i] + nums[l] + nums[r] > 0) {
               // 因为排序是从大到小的,如果当前的大于0,那么就让右指针往左移动,找小一点的!
               r -= 1
               // 如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[r] === nums[r + 1]) {
                   r -= 1
               }
           } else {
               // 如果找到了,那么就存起来,并且同时向内移动一位继续寻找!
               ret.push([nums[i], nums[l], nums[r]])
               l += 1;
               r -= 1;
               //  如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[l] === nums[l - 1]) {
                   l += 1
               }
               // 如果跳完了当前和上一个相同那么就多跳一次
               while (l < r && nums[r] === nums[r + 1]) {
                   r -= 1
               }
           }
       }
   }
   return ret;
};

image-1660368047212

0

评论区