双指针算法进阶
在处理有序数组相关的查找或统计问题时,双指针往往能带来线性的时间复杂度优化。本文将通过四个经典案例,从三角形计数到多数之和,梳理双指针的核心思路与去重技巧。
611. 有效三角形个数
题目描述
给定一个包含非负整数的数组,找出其中可以组成三角形的三元组个数。

核心思路
构成三角形的条件是任意两边之和大于第三边。若我们将三边排序为 $a \le b \le c$,只需满足 $a + b > c$ 即可。
利用这个性质,我们可以先对数组升序排序。固定最长边(第三边),然后使用双指针在剩余部分寻找满足条件的另外两边。
实现步骤
- 排序:将数组按升序排列。
- 固定最大边:从右向左遍历,将当前元素视为最长边 $c$。
- 双指针查找:左指针 $left$ 指向头部,右指针 $right$ 指向最大边左侧。
- 若 $nums[left] + nums[right] > nums[i]$,说明 $left$ 到 $right-1$ 之间的所有元素与 $right$ 组合都能满足条件(因为数组有序)。此时累加 $right - left$ 个解,并将 $right$ 左移。
- 若和小于等于 $nums[i]$,则 $left$ 需要右移以增大和。
- 终止条件:当 $left \ge right$ 时结束内层循环。

代码实现
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 升序排序
int count = 0;
// 从右往左依次将最大值作为第三边
( i = nums.() - ; i >= ; i--) {
left = ;
right = i - ;
(left < right) {
(nums[left] + nums[right] > nums[i]) {
count += right - left;
right--;
} {
left++;
}
}
}
count;
}
};






