611. 有效三角形的个数

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

排序 + 双指针

• 首先对数组排序。
• 固定最长的一条边，运用双指针扫描
  • 如果 nums[l] + nums[r] > nums[i]，同时说明 nums[l + 1] + nums[r] > nums[i], ..., nums[r - 1] + nums[r] > nums[i]，满足的条件的有 r - l 种，r 左移进入下一轮。
  • 如果 nums[l] + nums[r] <= nums[i]，l 右移进入下一轮。
• 枚举结束后，总和就是答案。
• 时间复杂度为 O(n^2)。

为什么要排序？

对于任意三角形，其三边 a, b, c 必须满足： a+b>c、a+c>b、b+c>a

对数组进行排序后，有 a≤b≤c，所以只需要验证 a+b>c 即可。

根据上面这个不等式我们就可以看出需要固定最大值c，然后用双指针查找a和b。

class Solution {
    public int triangleNumber(int[] nums) {
        // 对数组进行排序，便于后续使用双指针进行操作。重点。
        Arrays.sort(nums);
        
        int n = nums.length;  // 数组的长度
        int res = 0;  // 用于记录能够组成三角形的三元组数量

        // 从后往前遍历数组，固定一个元素 nums[i] 作为三角形的最长边
        for (int i = n - 1; i >= 2; --i) {
            int l = 0;  // 左指针，从数组开头开始
            int r = i - 1;  // 右指针，从当前元素的前一个位置开始

            // 使用双指针法寻找满足条件的三角形
            while (l < r) {
                // 如果左指针和右指针所指的元素之和大于固定的 nums[i]，
                // 说明 nums[l] 到 nums[r] 之间的所有元素都能与 nums[r] 组成三角形
                if (nums[l] + nums[r] > nums[i]) {
                    // 将满足条件的组合数累加到结果中，这些组合是{l,r},...,{r-1,r}
                    res += r - l;
                    // 右指针左移，尝试下一个较小的边
                    --r;
                } else {
                    // 如果条件不满足，则需要更大的左边，左指针右移
                    ++l;
                }
            }
        }

        // 返回最终能够组成三角形的三元组数量
        return res;
    }
}

时间复杂度为 O(n^2)。空间复杂度O(logn)