005_专题一_双指针_有效三角形的个数Java

目录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使用第一个22,3,4使用第二个22,2,3示例2输入nums [4,2,3,4]输出41.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判断是否能构成三角形满足abc​ 即可因为 acb、bca由 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)思路固定最大的数​ c从数组末尾开始遍历在 c的左侧区间即比 c小的数用双指针快速统计满足 abc的三元组个数。双指针逻辑手写推导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)。三角形判定排序后只需验证 abca≤b≤c。通过上述步骤即可高效解决“有效三角形的个数”问题。