前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

给你一个包含 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]]
示例 2：

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

输入：nums = [0]
输出：[]

提示：

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

1. 双指针法

思路（定义变量）

1. 先将数组从小到大排序，然后使用三个指针指向数组的不同位置。

• i作为起始指针。
• left和right分别为起始指针后面区域的头尾指针。

2. result作为返回的vector>

2. 本题思路分析（较为复杂，直接看卡哥的解析）：

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

3. 算法实现

• 代码：

#include  
#include 
#include 
#include 
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
	//双指针法
	vector<vector<int>>	result;
	//排除特例
	if(nums.size() < 3){
		return result;
	}
	//记得要排序
	sort(nums.begin(),nums.end());//引入algorithm 
	for(int i = 0,left = i + 1,right = nums.size() - 1;i < nums.size() - 2;i++,left = i + 1,right = nums.size() - 1){
		//排序后排除特例
		if(nums[i] > 0) {
			return result;
		}
		//**先去 i 的重** 
		if(i > 0 && nums[i] == nums[i - 1]){
			continue;
		}
		while(left < right){
			if(nums[i] + nums[left] + nums[right] > 0){//太大了 
				right--;
			}else if(nums[i] + nums[left] + nums[right] < 0){//太小了 
				left++;
			}else{
				vector<int> v = {nums[i],nums[left],nums[right]};
				result.push_back(v);
				//去重
				while(left < right && nums[left] == nums[left + 1]) left++;
				while(left < right && nums[right] == nums[right - 1]) right--;
				left++;
				right--;
			}
		}
	}
	return result;
}
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

4. 算法复杂度

1. 时间复杂度：O(n^2)
2. 空间复杂度：O(1)

5. 算法坑点

1. 此题题目中对于三个指针的去重问题。

对于起始指针i的去重问题

//先去 i 的重
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}

对于left、right指针的去重问题

while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right–;

2. 此题目对于特殊情况的处理

//排除特例
if(nums.size() < 3){
return result;
}

//排序后循环中排除特例
if(nums[i] > 0) {
return result;
}