Skip to content

3sum.md

Latest commit

 

History

History
181 lines (125 loc) · 5.04 KB

3sum.md

File metadata and controls

181 lines (125 loc) · 5.04 KB

15. 3Sum - 三数之和

Tags - 题目标签

Description - 题目描述

EN:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

 

Constraints:

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

ZH-CN:

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

 

 

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

 

提示：

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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language Runtime Memory Submission Time
typescript 148 ms 48.1 MB 2021/11/03 22:37 
function threeSum(nums: number[]): number[][] {
  const len = nums.length; 
  if (len < 3) {
    return [];
  } else if (len === 3) {
    return nums[0]+nums[1]+nums[2] === 0 ? [nums] : [];
  }

  const sortedNums = [...nums].sort((a, b) => a - b);


  const ans: Array<Array<number>> = [];

  for (let idx = 0; idx < len; idx++) {
    if (sortedNums[0] > 0) {
      break;
    }

    const target = -sortedNums[idx];


    if (sortedNums[idx] === sortedNums[idx-1]) {
      continue;
    }

    let i = idx+1, j = len - 1;
    while (i < j) {
      if (sortedNums[i] + sortedNums[j] === target) {
        ans.push([sortedNums[idx], sortedNums[i], sortedNums[j]]);
        i++;
        j--;
        while (sortedNums[i] === sortedNums[i-1] && i < j) {
          i++;
        }
        while (sortedNums[j] === sortedNums[j+1] && i < j) {
          j--;
        }
      } else if (sortedNums[i] + sortedNums[j] < target) {
        i++;
      } else {
        j--;
      }
    }
  }
  return ans;
};

My Notes - 我的笔记

思路：

排序后，从0到数组末尾遍历，固定一个 target，然后双指针在 target 后面寻找两数之和为 -target 的两个数字。

首指针为取 target 的索引 + 1， 尾指针为数组末尾。

遇到相加大于 -target 的，移动尾指针；小于 -target 时，移动首指针。等于 target 时，push 一个答案，首尾指针同时移动。

直到双指针碰头为止，开启下一轮循环。

注意：因为不可以包含重复的三元组，所以排序后的数组的元素遇到与它前面的元素重复时，跳过本轮循环。