【专题刷题】双指针（三）：两数之和，三数之和，四数之和

📝前言说明：

本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

视频

167. 两数之和 II
- 个人解
- 优质解
15. 三数之和
- 个人解
- 优质解
18. 四数之和
- 个人解
- 优质解

167. 两数之和 II

在这里插入图片描述

个人解

思路：
暴力求解的时间复杂度：O($n^2$)，每次移动只能获取一个信息，移动 $n^2$ 次，才能得到所有两数相加的结果。

那使用双指针呢？

使用双指针，利用数组的非递减性（也就是非严格单调递增性）
我们让一个指针指向左边最小的元素，一个指针指向右边最大的元素
要寻找numbers[left] + numbers[right] == target，
以numbers[left] + numbers[right] > target的时候为例，让right--，移动一次得到n个信息，因为当最小数和numbers[right]相加都大于target了，那其他numbers[left]之后更大的数与numbers[right]相加就没有意义了，一下可以排除n个数。left++也同理

用时：3:00
屎山代码：

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int left = 1, right = numbers.size();while(left < right){int sum = numbers[left - 1] + numbers[right - 1];if(sum < target)left++;else if(sum > target)right--;elsereturn {left, right};}return {-1,-1};}
};

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

优质解

简单题简单做，双指针已够用

15. 三数之和

在这里插入图片描述

个人解

思路：用base遍历整个数组，作为基准，将问题转换成nums[left] + nums[right] = 0 - nums[base]的问题。然后基于这个标准（nums[left] + nums[right] = 0 - nums[base]），再利用数组的单调性，再次用双指针。

用时：20:00（为什么这么长，因为题目要求不能重复，被去重坑惨了）
屎山代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {ranges::sort(nums);int n = nums.size(), base = 0;vector<vector<int>> ans;for(; base < n - 2; base++){int left = base + 1, right = n - 1;while(left < right){if(nums[base] + nums[left] + nums[right] < 0)left++;else if(nums[base] + nums[left] + nums[right] > 0)right--;else{ans.push_back({nums[base], nums[left], nums[right]});while(left < right && nums[left + 1] == nums[left])left++;while(left < right && nums[right - 1] == nums[right])right--;left++;right--;}}while(base < n - 3 && nums[base + 1] == nums[base])base++;}return ans;}
};

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

优质解

思路：双指针已经够用
但是我们来欣赏一下别人处理重复元素的思路，以及其他优化，和优雅的代码
代码（来自Leetcode上灵茶山艾府）：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {ranges::sort(nums);vector<vector<int>> ans;int n = nums.size();for (int i = 0; i < n - 2; i++) {int x = nums[i];// 跳过重复数字，base在使用前确保是唯一的，数组中无重复if (i && x == nums[i - 1]) continue; // 优化一（加上两个最小数）if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化二（加上两个最大数）if (x + nums[n - 2] + nums[n - 1] < 0) continue; int j = i + 1, k = n - 1;while (j < k) {int s = x + nums[j] + nums[k];if (s > 0) {k--;} else if (s < 0) {j++;} else { // 三数之和为 0ans.push_back({x, nums[j], nums[k]});// 跳过重复数字（用 for 可以多跳一步，直接跳到不相等的下一个元素）for (j++; j < k && nums[j] == nums[j - 1]; j++); for (k--; k > j && nums[k] == nums[k + 1]; k--);}}}return ans;}
};

18. 四数之和

个人解

在这里插入图片描述
思路：借助三数之和的解决方法，定好一个base以后又转换成三数之和的问题。
不过这时候优化的地方有两个，因为其实可以看做是有两个base
用时：19:00

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {ranges::sort(nums);vector<vector<int>> ans;int n = nums.size();for(int base = 0; base < n - 3; base++){   // 错误示范：应该要先用完再去除，因为万一其他数用的和base一样呢？// if(base < n - 4 && nums[base + 1] == nums[base])//     continue; // 去除重复元素if(base && nums[base] == nums[base - 1])continue;long long x = nums[base]; // 这题老六 数字会溢出if(x + nums[base + 1] + nums[base + 2] + nums[base + 3] > target)break;if(x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;for(int i = base + 1; i < n - 2; i++){if(i > base + 1 && nums[i] == nums[i - 1])continue;long long y = nums[i];if(x + y + nums[i + 1] + nums[i + 2] > target)break;if(x + y + nums[n - 2] + nums[n - 1] < target) continue;int j = i + 1, k = n - 1;while(j < k){if(x + y + nums[j] + nums[k] < target)j++;else if(x + y + nums[j] + nums[k] > target)k--;else{ans.push_back({(int)x, (int)y, nums[j], nums[k]});for(j++; j < k && nums[j] == nums[j - 1]; j++);for(k--; j < k && nums[k] == nums[k + 1]; k--);}}}}return ans;}
};