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