【算法一周目】双指针（2）
目录
有效三角形的个数
解题思路
C++代码实现
和为s的两个数字
解题思路
C++代码实现
三数之和
解题思路
C++代码实现
四数之和
解题思路
C++代码实现
有效三角形的个数
题目链接：611. 有效三角形的个数
题目描述：给定一个包含非负整数的数组nums，返回其中可以组成三角形三条边的三元组个数。
解题思路
首先对于三条边能否构成三角形，其条件就是任意两边之和大于第三边或者任意两边之差小于第三边，也就是说对于任意的正整数a、b、c，如果a + b > c且a + c > b且b + c > a，那么a、b、c就能构成三角形。但是用a、b、c运算3次有点过于冗余，所以需要优化下。
假如a、b、c是有序的也就是a <= b <= c，那么只需要判断a + b > c就能直到能否构成三角形，因为a + b > c成立，c是最大的数，那么a + c > b和b + c > a必然成立。
解法一：排序+暴力求解
先排序，然后用3层for循环枚举所有的三元组。判断是否能构成三角形。
class Solution {public: int triangleNumber(vector& nums) { // 1. 排序 sort(nums.begin(), nums.end()); int n = nums.size(), ret = 0; // 2. 从小到大枚举所有的三元组 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k nums[k]) ret++; } } } return ret; }};这样做时间复杂度是O(n ^ 3)，必然会超时。
解法二：排序+双指针
- 先对数组排序
- 固定一个最长边，然后在比这条边小的有序数组种找出一个二元组，使二元组之和大于这个最长边，由于数组有序，可以使用双指针。
- 设最长边枚举到位置 i ，区间 [left, right] 是 i 位置左边的区间（也就是比它小的区间）：
- 如果 nums[left] + nums[right] > nums[i]:
- 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比 nums[i] 大的二元组。
- 满足条件的有 right - left 种。
- 此时 right 位置的元素的所有情况相当于全部考虑完毕，right-- 进入下一轮判断。
- 如果 nums[left] + nums[right] <= nums[i]:
- 说明 left 位置的元素不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组。
- left 位置的元素可以舍去，left++ 进入下一轮循环。
C++代码实现
class Solution {public: int triangleNumber(vector& nums) { // 1. 排序 sort(nums.begin(), nums.end()); //2.双指针 int ret = 0; for(int i = nums.size() - 1; i >= 2; --i) //固定最大数 { //利⽤双指针快速统计符合要求的三元组的个数 int left = 0, right = i - 1; while(left nums[i]) { ret += right - left; right--; } else { left++; } } } return ret; }};时间复杂度：O(n ^ 2)，排序的时间复杂度为 O(n log n)，之后每个元素使用双指针进行一次遍历，时间复杂度为 O(n ^ 2)。
空间复杂度：O(log n)，排序的栈开销。
和为s的两个数字
题目链接：剑指 Offer 57. 和为s的两个数字
题目描述：输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。
解题思路
解法一：暴力枚举
两层for循环列出所有数字的组合，判断是否等于目标值。
class Solution {public: vector twoSum(vector& nums, int target) { int n = nums.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] + nums[j] == target) return {nums[i], nums[j]}; } } return {-1, -1}; }};解法二：双指针
1.初始化left、right指向数组左右两端。
2.当left < right，执行循环。
3.若nums[left] + nums[right] == target，说明找到结果，直接返回；
若nums[left] + nums[right] < target，当前和小于目标值，需要增大和，left++；
若nums[left] + nums[right] > target，当前和大于目标值，需要减小和，right--；
C++代码实现
class Solution {public: vector twoSum(vector& price, int target) { int left = 0, right = price.size() - 1; while(left target) right--; else if(price[left] + price[right] < target) left++; else break; } return {price[left], price[right]}; }};时间复杂度：O(n)
空间复杂度：O(1)
三数之和
题目链接：15. 三数之和
题目描述：给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解题思路
解法：排序+双指针
这道题与双指针类似，可以利用双指针思想来优化暴力枚举。
1.先排序
2.固定一个数a；
3.然后在这个数后面的区间内，使用双指针快速找到两个数之和等于 -a。
注意，该题是需要有去重操作：
1.找到一个结果后，left 和 right 指针要跳过重复元素。
2.使用完一次双指针后，固定的数a也要跳过重复的元素。
C++代码实现
class Solution {public: vector<vector> threeSum(vector& nums) { //1.去重 sort(nums.begin(), nums.end()); //2.双指针 int n = nums.size(); vector<vector> vv; for(int i = 0; i < n; ++i) //固定数 { //使用完双指针后的去重操作 while(i && i 0) break; //小优化 int left = i + 1, right = n - 1; int sum = -1 * nums[i]; while(left sum) right--; else if(nums[left] + nums[right] < sum) left++; else { vv.push_back({nums[i], nums[left], nums[right]}); left++, right--; //left和right跳过重复元素 while(left < right && nums[right + 1] == nums[right]) right--; while(left < right && nums[left - 1] == nums[left]) left++; } } } return vv; }};时间复杂度：O(n ^ 2)
空间复杂度：O(log n)，排序的栈开销
四数之和
题目链接：18. 四数之和
题目描述：给你一个由 n 个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）
解题思路
解法：排序+双指针
这道题是三数之和的升级版，解法是类似的，注意去重操作就可以的。
1.排序。
2.依次固定一个数a。
3.在a后面的区间，利用三数之和找到三个数，使得三个数的和等于target - a即可。
C++代码实现
class Solution {public: vector<vector> fourSum(vector& nums, int target) { vector<vector> ans; //1.排序 sort(nums.begin(), nums.end()); //2.利用双指针解决问题 int n = nums.size(); for(int i = 0; i < n; i++) //固定 a { //去重 a while(i && i < n && nums[i] == nums[i - 1]) i++; if(i == n) break; //三数之和的做法 for(int j = i + 1; j < n; j++) //固定 b { //去重 b while(j != 1 && j < n && j - 1 != i && nums[j] == nums[j - 1]) j++; if(j == n) break; int left = j + 1, right = n - 1; long long sum = (long long)target - nums[i] - nums[j]; while(left sum) right--; else if(nums[left] + nums[right] < sum) left++; else { ans.push_back({nums[i], nums[j], nums[left], nums[right]}); left++, right--; // 去重 left 和 right while(left < right && nums[left] == nums[left - 1]) left++; while(left < right && nums[right] == nums[right + 1]) right--; } } } } return ans; }};时间复杂度：O(n ^ 3)
空间复杂度：O(log n)，排序的栈开销
拜拜，下期再见😏
摸鱼ing😴✨🎞
