前言

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

题目

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

1. 双指针法

思路（定义变量）

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

• i,j分别作为双层循环的起始指针。
• left和right分别为起始指针后面区域的头尾指针。

2. result作为返回的vector>

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

此处略

3. 算法实现

• 代码：

#include  
#include 
#include 
#include 
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
	vector<vector<int>> result;
	int left = 0,right = 0;
	//剪枝操作 
	if(nums.size() < 4){
		return result;
	}
	//对nums进行排序 
	sort(nums.begin(),nums.end());
	for(int i = 0;i < nums.size() - 3;i++){
		//剪枝
		if(nums[i] > target && nums[i] >= 0 && target >= 0){
			return result;
		}
		//去重
		if(i > 0 && nums[i] == nums[i - 1]){
			continue;
		}
		for(int j = i + 1;j < nums.size() - 2;j++){
			//2级剪枝处理
			 if(nums[i] + nums[j] > target && nums[i] + nums[j] >= 0 && target >= 0){
			 //***坑点****(不是return result;因为是nums[i]+nums[j]两数之和,break到i的下一轮,虽然i变大了,但是j可能变小(j又重新回到i+1),导致nums[i]+nums[j]两数之和整体变小)
			 	break;
			 }
			 //2级去重
			 if(j > i + 1 && nums[j] == nums[j - 1]) {
			 	continue;
			 }
			 left = j + 1;
			 right = nums.size() - 1;
			 //双指针
			 while(left < right) {
			 	if((long) nums[i] + nums[j] + nums[left] + nums[right]> target){
			 		right --;
				}else if( (long) nums[i] + nums[j] + nums[left] + nums[right] < target){
					left ++;
				}else{
					vector<int> tmp = {nums[i],nums[j],nums[left],nums[right]};
					result.push_back(tmp);
					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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

4. 算法复杂度

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

5. 算法坑点

1. 二级剪枝时，应该是break，不是return result;因为是nums[i]+nums[j]两数之和,break到i的下一轮,虽然i变大了,但是j可能变小(j又重新回到i+1),导致nums[i]+nums[j]两数之和整体变小。
2. 循环的边界值问题，代码如下
   for(int i = 0;i < nums.size();i++){}
   cout << nums[i];
   }
   i会遍历到nums中所有的元素下标
   如果想到某个下标停止，比如到倒数第4个下标停止(包括第4个)，则让边界值为i < nums.size() - 3 (这里有可能会写错) 。
   因为当i = nums.size() - 1时,nums[i]为数组最后一个元素；
   则当i = nums.szie() - 3时，nums[i]为数组的倒数第3个元素；
   则当i < nums.size() - 3时，意味着i = nums.size() - 4，nums为倒数第4个元素；
   for(int i = 0;i < nums.size() - 3;i++){
   cout << nums[i];
   }
3. int越界问题
   多个int值相加的和仍为int类型，int最大值为2147483647≈2.14*10^9，超过这个数，就需要转换到long类型。（long类型的最大值约等于为 9.22 * 10 ^ 18 ，详见）
4. 当小精度和大精度的数进行运算，那么小精度的数在运算的时候会转化成大精度的数，并且运算结果也会自动转化成大精度的类型。

vector< int> nums;
(long) nums[i] + nums[j] + nums[left] + nums[right]
nums[i]是int类型，被显性转化成long类型，然后long类型和int类型运算，结果被隐形转化成long类型（自动转换成高精度类型）

相关链接：C++中的类型转换
java中的类型转换
5. 此题题目中对于四个指针的去重问题。
详见卡哥