💬 欢迎讨论:如有疑问或见解,欢迎在评论区留言互动。 👍 点赞、收藏与分享:如觉得这篇文章对您有帮助,请点赞、收藏并分享! 🚀 分享给更多人:欢迎分享给更多对 C++ 感兴趣的朋友,一起学习双指针的基础与进阶!
接上篇【优选算法篇】双指针的优雅舞步:C++ 算法世界的浪漫探索
本篇文章将带领大家进入双指针的进阶领域。在基础篇中,我们已经学习了如何利用双指针优化简单数组问题,而在这一篇中,我们将进一步深入探讨双指针的高级应用场景,包括排序问题、多数之和等经典题型的双指针解法,以及如何利用双指针快速解决复杂的数组与链表问题。
通过更加深入的题目分析和双指针的高级策略,我们希望大家能够更加熟练地运用这一算法技巧,应对更具挑战性的编程问题。让我们继续双指针的优雅舞步,开启 C++ 算法世界的浪漫探索!
题目链接:611. 有效三角形的个数
题目描述:给定一个包含非负整数的数组 nums
,返回其中可以组成三角形三条边的三元组个数。
nums = [2, 2, 3, 4]
3
nums = [4, 2, 3, 4]
4
算法思路:
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)
,对于较大的输入,三层循环会导致性能问题,适合小规模数据。O(1)
,只使用了常数个变量存储结果和中间值。算法思路:
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++
进入下一轮循环。代码实现:
class Solution {
public:
int triangleNumber(vector<int>& nums) {
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利用双指针解决问题
int ret = 0, n = nums.size();
for (int i = n - 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(1)
,只使用了常数个变量存储结果和指针位置。left
或 right
,确保找到所有满足条件的三元组。该算法的时间复杂度为 O(n^2)
,空间复杂度为 O(1)
,适合大规模输入。通过排序和双指针优化,能够有效减少暴力求解中的不必要计算,提升性能。此方法非常适合在数组问题中应用,能够快速找到所有满足条件的组合。
题目链接:剑指 Offer 57. 和为s的两个数字
题目描述:输入一个递增排序的数组和一个数字 s
,在数组中查找两个数,使得它们的和正好是 s
。如果有多对数字的和等于 s
,则输出任意一对即可。
nums = [2, 7, 11, 15], target = 9
[2, 7]
或者 [7, 2]
算法思路:
for
循环列出所有两个数字的组合,判断是否等于目标值。算法流程:
for
循环: for
循环依次枚举第一个数 a
;for
循环依次枚举第二个数 b
,让它与 a
匹配;代码实现:
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};
}
};
算法思路:
算法流程:
left
,right
分别指向数组的左右两端: left < right
的时候,一直循环: nums[left] + nums[right] == target
时,说明找到结果,记录结果,并返回;nums[left] + nums[right] < target
时: left++
;nums[left] + nums[right] > target
时: right--
。代码实现:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum > target) right--;
else if (sum < target) left++;
else return {nums[left], nums[right]};
}
//这是为了照顾编译器,不然编译器报错:不是所有的路径都有返回值
return {-1, -1};
}
};
题目链接:15. 三数之和
题目描述:给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
nums = [-1, 0, 1, 2, -1, -4]
[[-1, -1, 2], [-1, 0, 1]]
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
。[-1, 0, 1]
和 [-1, -1, 2]
。nums = [0, 1, 1]
[]
nums = [0, 0, 0]
[[0, 0, 0]]
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
算法思路:
a
;-a
即可。left
和 right
指针要「跳过重复」的元素;a
也要「跳过重复」的元素。代码实现:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利用双指针解决问题
int n = nums.size();
for (int i = 0; i < n; ) { // 固定数 a
if (nums[i] > 0) break; // 小优化
int left = i + 1, right = n - 1, target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum > target) right--;
else if (sum < target) left++;
else {
ret.push_back({nums[i], 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--;
}
}
// 去重 i
i++;
while (i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};
题目链接:18. 四数之和
题目描述:给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和 d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。
nums = [1, 0, -1, 0, -2, 2]
, target = 0
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
nums = [2, 2, 2, 2, 2]
, target = 8
[[2, 2, 2, 2]]
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
算法思路:
a
;a
的后面区间上,利用「三数之和」找到三个数,使这三个数的和等于 target - a
即可。代码实现:
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--]});
// 去重操作 left 和 right
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
// 去重 j
j++;
while (j < n && nums[j] == nums[j - 1]) j++;
}
// 去重 i
i++;
while (i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};
在本篇文章中,我们沿着双指针的足迹,走进了更为复杂的算法世界。从基础的排序与两数之和,到多元问题的优化解法,双指针以其灵活而高效的策略,为我们提供了简洁优雅的解题思路。无论是解锁数组中的隐藏结构,还是精确处理链表中的循环,双指针始终如同算法中的舞者,轻巧地穿梭于问题的复杂性之间,帮助我们化繁为简。
希望通过这些进阶题解,大家能不仅熟悉双指针的运用技巧,更能深刻体会到算法设计中的思维之美。未来的算法旅程中,无论面对怎样的挑战,双指针这一工具都能在你的编程工具箱中,成为应对复杂问题时得心应手的利器。
以上就是关于【优选算法篇】双指针的华丽探戈:深入C++算法殿堂的优雅追寻的内容啦,各位大佬有什么问题欢迎在评论区指正,或者私信我也是可以的啦,您的支持是我创作的最大动力!❤️