三数之和
https://leetcode.cn/problems/3sum/description/
双指针法
思路
1、拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
2、依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
3、接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
4、如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
去重
a去重逻辑
当前遍历元素和前一个元素重复是，跳过
b和c去重逻辑
- 如果当前left元素和left++对一个的元素相同，left++跳过。同理right和right–元素对比。
- 当然如果不相同，left++的同时right–
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
| var threeSum = function(nums) {
let res = [];
nums.sort((a,b)=>a-b);
for(let i=0;i<nums.length-2;i++){
if (nums[i] > 0) return
if(i>0 && nums[i]===nums[i-1]) continue;
let left = i+1;
let right = nums.length-1;
while(left<right){
let sum = nums[i] + nums[left] + nums[right];
if (sum > 0) right--;
if (sum < 0) left++;
if(sum === 0){
res.push([nums[i],nums[left],nums[right]]);
while(left<right && nums[left] === nums[left+1]) left++;
while(left<right && nums[right] === nums[right-1]) right--;
left++;
right--;
}
}
}
return res;
};
|
回溯算法
我的初始想法是用回溯算法，但是这个方法在处理较长的数组时会超时。
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
|
var threeSum = function(nums) {
let res = [];
let path =[];
nums = nums.sort((a,b)=>a-b);
const backTraking = (nums,startIndex)=>{
if(path.length === 3){
if(path[0]+path[1]+path[2] === 0){
res.push([...path])
}
return;
}
if (path.length === 0 && nums[startIndex] > 0) return;
if (path.length === 1 && nums[startIndex]+path[0] > 0) return;
if (path.length === 2 && nums[startIndex]+path[0]+path[1]>0) return;
for(let i=startIndex;i<nums.length;i++){
if(i>startIndex && nums[i] === nums[i-1]){
continue;
}
path.push(nums[i]);
backTraking(nums,i+1);
path.pop();
}
}
backTraking(nums,0);
return res
};
|