双指针算法：有效三角形的个数

题目描述

给定一个包含非负整数的数组，统计其中能组成三角形三元组的个数。

解题思路

判断三角形的条件是任意两边之和大于第三边。若数组已排序，只需验证较小两边之和是否大于最大边。

暴力解法

直接三重循环遍历所有组合，时间复杂度为 O(n^3)。

双指针优化

1. 对数组进行升序排序。
2. 从后向前固定最大边 nums[i]。
3. 使用双指针 left 和 right 分别在 i 之前移动。
4. 若 nums[left] + nums[right] > nums[i]，则 left 到 right-1 之间的数均满足条件，累加计数并右指针左移。
5. 否则左指针右移。

代码实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ret = 0, n = nums.size();
        for (int i = n - 1; i >= 0; 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;
    }
};