优先算法 —— 双指针系列 - 四数之和

前言

本题除了多加了一个数之外，其他都与三数之和的思路相同

  

优先算法 —— 双指针系列 - 三数之和-CSDN博客https://blog.csdn.net/hedhjd/article/details/144129358?spm=1001.2014.3001.5502

1. 四数之和

题目链接：

   

18. 四数之和 - 力扣（LeetCode）https://leetcode.cn/problems/4sum/description/

2. 题目解析 

以示例1为例：

  

  

3. 算法原理

解法1：暴力枚举

  

排序 + 暴力枚举 + 使用set进行去重  

我们可以先进行排序，这样我们枚举之后就会发现如果有相同的那么枚举出来的值是一样的

  

但是这个解法和三数之和一样是绝对会超时的，所以我们直接跳过

解法2：双指针算法

 排序 + 双指针

我们在暴力枚举的基础上进行优化，我们进行了排序，那么数组就变成了有序的，如果是有序的数组，那么我们一般使用 二分 或者 双指针 来解决，一般能够使用双指针来解决问题就不要使用二分

  

  

处理细节问题：

  

不重复，本题有三个去重：

   

1. 使用双指针时，当我们找到一个结果的时候，left和right要进行一次去重

  

2. 当使用完双指针之后，b也要进行去重

  

3. 当使用完三数之和之后，a也要进行去重

  

  

4. 代码

class Solution
{
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target)
	{
		vector<vector<int>> ret;
		// 1. 排序
		sort(nums.begin(), nums.end());
		// 2. 利⽤双指针解决问题
		int n = nums.size();
		for (int i = 0; i < n; ) // 固定数 a
		{
			// 利⽤ 三数之和
			for (int j = i + 1; j < n; ) // 固定数 b
			{
				// 双指针
				int left = j + 1, right = n - 1;
				long long aim = (long long)target - nums[i] - nums[j];
				while (left < right)
				{
					int sum = nums[left] + nums[right];
					if (sum < aim) left++;
					else if (sum > aim) right--;
					else
					{
						ret.push_back({ nums[i], nums[j], nums[left++],
						nums[right--] });
						// 去重⼀
						while (left < right && nums[left] == nums[left - 1])
							left++;
						while (left < right && nums[right] == nums[right + 1])
							right--;
					}
				}
				// 去重⼆
				j++;
				while (j < n && nums[j] == nums[j - 1]) j++;
			}
			// 去重三
			i++;
			while (i < n && nums[i] == nums[i - 1]) i++;
		}
		return ret;
	}
};

双指针系列的题目就先到此为止~