15\. 三数之和
# 15. 三数之和 (opens new window)
# Description
Difficulty: 中等
Related Topics: 数组 (opens new window), 双指针 (opens new window), 排序 (opens new window)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 _a，b，c ，_使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
1
2
2
示例 2：
输入：nums = []
输出：[]
1
2
2
示例 3：
输入：nums = [0]
输出：[]
1
2
2
提示：
0 <= nums.length <= 3000- -105 <= nums[i] <= 105
# Solution
Language: JavaScript
/**
* @param {number[]} nums
* @return {number[][]}
* 1.暴力解法
* 三重循环
*
* 2.双指针法
* 关键字：不可以包含重复
* 模式识别：利用排序避免重复答案
* 降低复杂度变成twoSum
* 利用双指针找到所有解
*
* 先将数组进行排序，自左向右进行搜索，从小到大搜索，跳过重复值
* 找到目标和，加入解
* 移动指针
* 如果和比目标值小，移动头指针，否则移动右指针
* 排除重复项
*
* 方法一：排序 + 双指针
*/
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans = [];
for (let i = 0; i < n - 2; i++) {
if (nums[i] > 0) break
if (i > 0 && nums[i] === nums[i-1]) continue
let [l, r] = [i+1, n-1]
while (l < r) {
const sum = nums[i] + nums[l] + nums[r]
if (sum === 0) {
ans.push([nums[i], nums[l], nums[r]])
while (l < r && nums[l] === nums[l+1]) l++
while (l < r && nums[r] === nums[r-1]) r--
l++
r--
} else if (sum < 0) {
while (l < r && nums[l] === nums[l+1]) l++
l++
} else {
while (l < r && nums[r] === nums[r-1]) r--
r--
}
}
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49