目录

1. 题目解析

1.1 题目描述（611. 有效三角形的个数）

1.2 手写分析

2. 算法原理

2.1 补充数学知识：三角形判定

2.2 优化思路：先排序

2.3 解法一：暴力枚举

2.4 解法二：双指针（利用单调性）

双指针逻辑（手写推导）：

3. 编写代码

总结

---

• OJ链接：https://leetcode.cn/problems/valid-triangle-number/

1. 题目解析

1.1 题目描述（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.2 手写分析

数组 [2,2,3,4]的有效组合分析：

• [2,2,3]✔️

• [2,2,4]❌

• [2,3,4]✔️（第一个 2）

• [2,3,4]✔️（第二个 2）

  最终有效个数为 3。

2. 算法原理

2.1 补充数学知识：三角形判定

给定三个数 a≤b≤c，判断是否能构成三角形：

满足 a+b>c​ 即可（因为 a+c>b、b+c>a由 a≤b≤c天然成立）。

2.2 优化思路：先排序

对数组排序后，可利用单调性简化判断。

2.3 解法一：暴力枚举

通过三层循环枚举所有三元组 (i,j,k)，时间复杂度 O(N^3)。

代码示例：

for(int i = 0; i < n; i++)
    for(j = i + 1; j < n; j++)
        for(k = j + 1; k < n; k++)
            check(i,j,k) // 判断是否满足三角形条件

2.4 解法二：双指针（利用单调性）

时间复杂度优化到 O(N^2)，思路：

1. 固定最大的数​ c（从数组末尾开始遍历）；

2. 在 c的左侧区间（即比 c小的数），用双指针快速统计满足 a+b>c的三元组个数。

双指针逻辑（手写推导）：

3. 编写代码

以下是基于双指针的Java实现：

class Solution {
    public int triangleNumber(int[] nums) {
        // 1. 优化：排序
        Arrays.sort(nums);
        
        // 2. 利用双指针解决问题
        int ret = 0, n = nums.length;
        for (int i = n - 1; i >= 2; 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;
    }
}

总结

• 核心思路：排序 + 双指针，利用单调性将时间复杂度从 O(N^3)降到 O(N^2)。

• 三角形判定：排序后只需验证 a+b>c（a≤b≤c）。

通过上述步骤，即可高效解决“有效三角形的个数”问题。