C++算法：双指针篇（下）

一、有效三角形的个数1.题目2.核心思路三角形三边条件对于三条边 (a,b,c)需要满足 (abc,acb,bca)。 先将数组升序排序。排序后固定nums[tar]作为最长边此时 (nums[tar]) 是三元组里最大值自动满足 (anums[tar]b)、(bnums[tar]a)只需要满足 (abnums[tar]) 即可构成三角形。采用双指针left初始在区间最左端最小数right在tar-1最长边前一位如果(nums[left]nums[right] nums[tar])说明从left到right-1的所有数和nums[right]配对都满足条件。一共有right-left组直接加到答案然后right--尝试更小的右边界。如果 (nums[left]nums[right] nums[tar])两数之和不够大left增大左值。外层循环tar从数组末尾向前枚举直到tar 2至少需要另外两个元素。3.举例模拟示例nums [2,2,3,4]排序后[2,2,3,4]\(n4\)ret0tar3nums[tar]4left0right2left0, right2nums[0]nums[2] 23 4 → ret 2-0 2ret2right1left0, right1nums [0]nums [1]22 444 不成立 → leftleft1。此时 left 不小于 right本轮 tar 循环结束。tar2nums[tar]3left0right1left0, right1nums [0]nums [1]223 → ret 1-01ret3right0循环结束。tar1 不满足 tar2外层循环结束。 最终答案 ret3。合法三元组(2,2,3)、(2,3,4)、(2,3,4)共 3 组。4.代码参考5..复杂度时间复杂度(O(n^2)) 排序(O(nlog n))外层 for 循环最多n次内层 while 双指针每个 tar 最多遍历一次内层总复杂度(O(n))整体(O(n^2))(nlog n)可以忽略。空间复杂度(O(log n)) 排序使用的栈开销没有额外开辟数组仅常数个变量。原地排序。二、两数之和1.题目2.核心思路给定升序有序数组寻找两个元素相加等于目标值target。 设置左右双指针left指向数组最左端最小元素right指向数组最右端最大元素若price[left]price[right] target总和太小左指针右移增大和若price[left]price[right] target总和太大右指针左移减小和若等于 target直接返回这两个数当left right还没找到说明不存在返回{-1,-1}。3.举例模拟示例price [2,7,11,15], target 9left0right3sum21517 9 → right-- → right2sum21113 9 → right-- → right1sum279 target → 返回[2,7]4.代码参考5..复杂度时间复杂度(O(n))。左右指针最多各移动 n 次一次遍历。注意如果原始数组无序需要先 sort 排序排序会带来\(O(n\log n)\)开销。空间复杂度(O(1))只使用常数额外变量。三、三数之和1.题目2.核心思路排序先把数组升序排序。排序后方便双指针移动同时方便跳过重复元素。固定第一个数 nums [a]循环枚举 a目标找nums[left]nums[right] -nums[a]记为 tar。a 去重如果当前nums[a]和前一个nums[a-1]相等直接 continue避免重复三元组。双指针lefta1rightnums.size()-1nums[left]nums[right] tar找到一组解存入结果然后跳过 left、right 侧重复数字再left,right--nums[left]nums[right] tar和太小left 右移增大和nums[left]nums[right] tar和太大right 左移减小和收集所有不重复三元组返回。3.举例模拟输入nums [-1,0,1,2,-1,-4]排序后[-4,-1,-1,0,1,2]ret 初始为空1. a0nums [a]-4tar4left1 (-1), right5 (2) sum-121 4 → left → left2 (-1), sum-1214 → left → left3 (0), sum0224 → left → left4 (1), sum1234 → leftleft 不再 right本轮无结果。2. a1nums [a]-1tar1left2 (-1), right5 (2) sum-121 tar。存入[-1,-1,2]left 去重nums [2]nums [3] -1≠0不进入循环 right 去重nums [5]nums [4]2≠1不进入循环 left,right-- → left3right4 现在 leftrightsum011 tar。存入[-1,0,1]left 去重nums [3]nums [4]0≠1 right 去重nums [4]nums [3]1≠0 left,right--leftright本轮结束。3. a2nums [a]-1a0 且 nums [a]nums [a-1](-1 -1)continue 跳过。4. a3nums.size()-24a3 4nums [a]0tar0left4right5sum120right--leftright无结果。 循环结束。 结果[[-1,-1,2],[-1,0,1]]4.代码参考5..复杂度时间复杂度(O(n^2)) 排序(O(nlog n))外层 for 循环 n 次内层双指针最多 O (n)(O(nlog n)O(n^2)O(n^2))。空间复杂度(O(log n)) 排序需要(log n)栈空间结果数组不计入额外空间开销。四、四数之和1.题目2.核心思路排序 两层循环固定前两个数 (a,b) 双指针 (c,d) 找后两个数1.先把数组排序方便去重和双指针移动。2.外层循环a固定第 1 个数跳过重复 a避免重复四元组 目标剩下三个数之和 tar1 target - nums[a]3.内层循环b固定第 2 个数从a1开始跳过重复 b 目标剩下两个数之和 tar2 tar1 - nums[b]4.双指针c b1左d n-1右在b右侧区间寻找两数之和等于tar2nums[c]nums[d] tar2找到一组解存入答案然后跳过 c、d 位置的重复元素再收缩指针c,d--和偏小c增大总和和偏大d--减小总和5.使用long long防止 int 数值相加溢出。6.本质把4 数之和降维成3 数之和再降维成2 数之和双指针。3.举例模拟样例nums [1,0,-1,0,-2,2], target 0排序后[-2,-1,0,0,1,2]n6 目标找 4 个数相加等于 0。1.a0nums [a]-2 tar1 0 - (-2) 2 b 从 a11 开始b1nums [b]-1tar2 2 - (-1)3 c2d5nums [c]0nums [d]2sum2 3 → c c3d5sum0223 → c c4,d5sum123 tar2 存入[-2,-1,1,2]c、d 去重c,d--c 不再小于 d双指针结束。b2nums [b]0tar22-02 c3,d5nums [3]0,nums [5]2 sum2 tar2 存入[-2,0,0,2]c,d--循环结束。b3nums[b]0ba1 nums[b]nums[b-1]→ 重复continue。2.a1nums [a]-1 a0 nums [a]nums [a-1]nums [-1]-2≠-1不跳过。 tar1 0 - (-1)1 b 从 a12 开始b2nums [b]0tar21-01 c3,d5nums [3]0,nums [5]2 sum21 → d-- c3,d4011 tar2 存入[-1,0,0,1]c,d--循环结束。3.a2nums[a]0a0 nums[a]nums[a-1]nums [1]-1≠0但是 an-3 → a2n-33a2 满足后续 b 循环找不到新解。4.a3an-3→ 33 不成立外层循环结束。最终结果[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]4.代码参考5.复杂度时间复杂度(O(n^3)) 排序(O(nlog n))两层循环 a,b 是(O(n^2))内部双指针 c,d 最多遍历一次数组(O(n))总的是 (O(n^3))。四数之和最优就是(O(n^3))无法到(O(n^2))。空间复杂度(O(log n)) 排序需要栈空间不计保存答案的 ret 数组额外空间为排序栈空间。五、总结共性前提数组排序是双指针、去重的基础核心思想固定一部分双指针在剩余区间相向收缩把暴力多层枚举降低复杂度相向双指针适用场景有序数组判断两数之和和目标值的大小关系通过移动左右指针调整总和。四个题对比1. 有序数组两数之和做法left0rightn-1相向移动目标nums[left]nums[right]target特点不涉及去重只找一组解无序数组直接用哈希表更方便2. 三数之和做法固定 a双指针lefta1, rightn-1找两数之和等于-nums[a]关键点a、left、right 去重防止重复三元组3. 四数之和做法固定 a、b 两层循环双指针cb1,dn-1找两数之和关键点a、b 去重必须 long long 防 int 溢出4. 有效三角形的个数特殊相向双指针思路排序后固定最长边 tar只需要判断短两边之和 最长边其余两个三角形条件自动成立技巧满足条件时一次性批量计数right-left 组不用逐个枚举效率更高