【算法一周目】双指针（2）
目录
有效三角形的个数
题目链接：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++;
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<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
{
//去重 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 < 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 和 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😴✨🎞
原文地址：https://blog.csdn.net/2301_80373479/article/details/143454985
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！