title

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题

相关思路:

  1. 排序;
  2. 查找表;
  3. 双指针;
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const sortNums = nums.sort((r1, r2) => r1 - r2)
let targetValue
const cacheMap = new Map()
const result = []
for (let i = 0; i < sortNums.length - 2; i++) {
targetValue = -sortNums[i]
let l = i + 1
let r = sortNums.length - 1
while (l < r) {
let tmpArr = []
const mapValue = cacheMap.get(`${-targetValue}${sortNums[l]}${sortNums[r]}`)
if (sortNums[l] + sortNums[r] === targetValue && !mapValue) {
tmpArr.push(-targetValue)
tmpArr.push(sortNums[l])
tmpArr.push(sortNums[r])
result.push(tmpArr)
cacheMap.set(`${-targetValue}${sortNums[l]}${sortNums[r]}`, true)
l++
r--
} else if (sortNums[l] + sortNums[r] === targetValue && mapValue) {
l++
}else if (sortNums[l] + sortNums[r] > targetValue) {
r--
}else if (sortNums[l] + sortNums[r] < targetValue) {
l++
}
}
}
return result
}

此时通过测试用例的情况为 312/313, 差一个包含 3000 个 0 数组的测试用例没通过; 根据评论区的提示, 缺少了对解进行去重这个步骤(卡主大部分人的原因), 优化如下:

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const sortNums = nums.sort((r1, r2) => r1 - r2)
let targetValue
const result = []
for (let i = 0; i < sortNums.length - 2; i++) {
// 针对下标 i 对应的值进行去重
if (i === 0 || nums[i] > nums[i - 1]) {
targetValue = -sortNums[i]
let l = i + 1
let r = sortNums.length - 1
while (l < r) {
let tmpArr = []
if (sortNums[l] + sortNums[r] === targetValue) {
tmpArr.push(-targetValue)
tmpArr.push(sortNums[l])
tmpArr.push(sortNums[r])
result.push(tmpArr)
l++
r--
// 针对下标 l 对应的值进行去重, r 同理
while (l < r && sortNums[l] === sortNums[l - 1]) {
l++
}
while (l < r && sortNums[r] === sortNums[r + 1]) {
r--
}
} else if (sortNums[l] + sortNums[r] > targetValue) {
r--
} else if (sortNums[l] + sortNums[r] < targetValue) {
l++
}
}
}
}
return result
}

Sister Title

1、16、18