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

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

题目描述

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

示例 1: 输入：[2,2,3,4] 输出：3 解释：有效的组合是：(2,3,4), (2,3,4), (2,2,3)

示例 2: 输入：[4,2,3,4] 输出：4

提示:

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

算法原理

三角形判定条件

对于三条边长 $a, b, c$，若满足任意两边之和大于第三边，则可构成三角形。当数组已排序且 $a \le b \le c$ 时，只需验证 $a + b > c$ 即可。

双指针优化策略

1. 排序：首先将数组升序排序。
2. 固定最长边：从后向前遍历，将当前元素视为三角形的最长边 c。
3. 双指针查找：设置左指针 left = 0，右指针 right = i - 1。
   • 若 nums[left] + nums[right] > nums[i]，说明 nums[right] 与 nums[left] 到 nums[right-1] 之间的所有元素均能构成有效三角形。累加数量 right - left，并将 right 左移。
   • 否则，nums[left] 过小，无法与 nums[right] 构成有效三角形，将 left 右移。
4. 复杂度：时间复杂度 $O(N^2)$，空间复杂度 $O(\log N)$（排序开销）。

代码实现

import java.util.Arrays;

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
           ;
           nums.length;
         (   n - ; i >= ; i--) {
               ;
               i - ;
             (left < right) {
                 (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    right--;
                }  {
                    left++;
                }
            }
        }
         count;
    }
}