15. 三数之和 - 力扣（LeetCode）

发布：2021年8月9日20:04:06

问题描述及示例

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

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

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

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

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

提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

我的题解

在这里插入图片描述

其实整体思路是在LeetCode两数之和那个题目上做一点改变得到的。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  // result用于存储最终结果
  let result = [];
  // 先将nums排序，这一步很关键，当然升序和降序都可以，只要后续逻辑进行相应改变即可
  nums.sort((a, b) => a - b);
  // 遍历nums数组，注意i的结束条件，因为要留两个位置给front和rear指针，
  // 其实这里按平常的 i < nums.length 来写也可以，但是会多两次无意义的遍历
  for(let i = 0; i < nums.length - 2; i++) {
    // 去重操作，又是关键的一步，避免等值的两个数组元素重复参与，i++ 可用continue代替
    while(nums[i] === nums[i-1]) {
      i++;
    }
    // target 相当于是两数之和题目中的target，从这里开始就是两数之和的题目的逻辑了
    let target = 0 - nums[i];
    // 前部的指针
    let front = i + 1;
    // 尾部的指针，注意：在一次遍历中，front和rear都是朝着数组中间移动
    let rear = nums.length - 1;
    // 若前指针保持在尾指针之前，则说明待校验的数组元素中还有可能有符合条件的元素
    while(front < rear) {
      if(nums[front] + nums[rear] === target) {
        // 如果当前遍历的元素nums[i]和front、rear两个指针指向的数组元素满足要求则将其加入结果集合
        result.push([nums[i], nums[front], nums[rear]]);
        // 下面两个while循环也都是用于去重，注意这个去重和上面那个去重不同
        while(front < rear && nums[front] === nums[front+1]) {
          front++;
        }
        while(front < rear && nums[rear] === nums[rear-1]) {
          rear--;
        }
        // front和rear指针都在该次遍历中被用过一次了，所以要同时将两个指针向中间移动一步
        rear--;
        front++;
      } else if(nums[front] + nums[rear] > target) {
        // 如果两个指针指向的元素值之和比目标值大，则试着将尾指针向前移动一位
        rear--;
      } else {
      	// 否则将前指针向后移动一位，注意这两种情况下的移动不能同时做
        front++;
      }
    }
  }
  return result;
};


提交记录
318 / 318 个通过测试用例
状态：通过
执行用时：124 ms, 在所有 JavaScript 提交中击败了98.50%的用户
内存消耗：48 MB, 在所有 JavaScript 提交中击败了45.81%的用户
时间：2021/08/09 20:00