【算法一周目】双指针（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<int>& 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 < n; k++) {// 当最小的两个边之和大于第三边的时候，统计答案if (nums[i] + nums[j] > 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<int>& 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 < right){if(nums[left] + nums[right] > 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<int> twoSum(vector<int>& 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<int> twoSum(vector<int>& price, int target) {int left = 0, right = price.size() - 1;while(left < right){if(price[left] + price[right] > target)right--;else if(price[left] + price[right] < target)left++;elsebreak;   }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<int>> threeSum(vector<int>& nums) {//1.去重sort(nums.begin(), nums.end());//2.双指针int n = nums.size();vector<vector<int>> vv;for(int i = 0; i < n; ++i)  //固定数{//使用完双指针后的去重操作while(i && i < n && nums[i - 1] == nums[i])i++;if(i == n) break;if(nums[i] > 0) break; //小优化int left = i + 1, right = n - 1;int sum = -1 * nums[i];while(left < right){if(nums[left] + nums[right] > 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<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;//1.排序sort(nums.begin(), nums.end());//2.利用双指针解决问题int n = nums.size();for(int i = 0; i < n; i++)  //固定 a{//去重 awhile(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 < right){if(nums[left] + nums[right] > 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 和 rightwhile(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😴✨🎞