前言
双指针配合排序是解决数组查找问题的利器。当数据有序时，利用两个指针向中间靠拢或同向移动，往往能将暴力解法的复杂度优化一个数量级。下面通过四个经典案例，演示如何固定一边或两边，在有序数组中快速定位目标组合。
611. 有效三角形个数
核心思路
构成三角形的条件是任意两边之和大于第三边。若设三边为 a, b, c（c 为最长边），则只需满足 a + b > c。
为了高效判断，我们先将数组升序排序。排序后，单调性变得清晰：每次固定最大值作为第三边，最左侧元素作为最短边，次大值作为最长边。此时若 nums[left] + nums[right] > nums[i]，由于数组有序，left 与 right 之间的所有元素与 nums[right] 相加必然大于 nums[i]，因此可以直接累加 right - left 个解。
实现要点
- 排序：升序排列，方便后续逻辑。
- 指针移动：外层循环从右向左固定最大边
i；内层left指向头，right指向i-1。 - 去重与边界：注意
i至少为 2，且left < right时继续搜索。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 升序排序
int count = 0;
// 从右往左依次将最大值作为第三边
for(int i = nums.size() - 1; i >= 2; i--) {
int left = 0; // 左指针（最短边）
int right = i - 1; // 右指针（最长边）
while(left < right) {
if(nums[left] + nums[right] > nums[i]) { // 两边之和大于第三边
count += right - left;
right--;
} {
left++;
}
}
}
count;
}
};