LeetCode|LeetCode_双指针_中等_611.有效三角形的个数 leetcode|双指针|排序|算法刷题

1.题目
2.思路
3.代码实现（Java）

1.题目给定一个包含非负整数的数组 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
【LeetCode|LeetCode_双指针_中等_611.有效三角形的个数】来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-triangle-number
2.思路（1）排序 & 暴力穷举法
排序 & 暴力穷举法比较容易想到，具体步骤如下：
① 先将数组 nums 进行升序排序；
② 使用 3 层 for 循环来枚举每一个三元组 (nums[i], nums[j], nums[k])，其中，nums[i] ≤ nums[j] ≤ nums[k]，所以如果 nums[i] + nums[j] > nums[k]，那么该三元组一定可以构成三角形；否则就构不成，需要注意的是，这里存在一个过滤操作，即如果 nums[k] ≥ nums[i] + nums[j]，由于数组 nums 已经是按升序排好的，所以后面的 nums[k] 肯定也 ≥ nums[i] + nums[j]，所以此时可以结束第 3 层循环；
③ 在穷举的过程中，使用变量 res 来记录组成三角形三条边的三元组个数，穷举结束后直接返回 res 即可。
（2）排序 & 双指针
思路参考本题官方题解。
① 先将数组 nums 进行升序排序；
② 使用 1 层 for 循环来枚举 i，当 i 固定时，维护双指针 left 和 right；
③ 再使用 1 层 for 循环来枚举 left，每次将 left 向右移动一个位置时，尝试不断地向右移动 right，使得 right 是最大的满足 nums[right] < nums[i] + nums[left] 的下标，然后再用 res += Math.max(right - left, 0) 来累加答案。
④ 当枚举结束后，直接返回 res 即可。
3.代码实现（Java）

//思路1————排序 & 暴力穷举法 class Solution { public int triangleNumber(int[] nums) { int res = 0; int length = nums.length; //将数组 nums 进行升序排序 Arrays.sort(nums); for (int i = 0; i < length - 2; i++) { for (int j = i + 1; j < length - 1; j++) { for (int k = j + 1; k < length; k++) { if (nums[i] + nums[j] > nums[k]) { res++; } else { //由于数组 nums 已经是按升序排好的，所以后面的 nums[k] 肯定也大于等于 nums[i] + nums[j] break; } } } } return res; } }

//思路2————排序 & 双指针 class Solution { public int triangleNumber(int[] nums) { int res = 0; int length = nums.length; Arrays.sort(nums); for (int i = 0; i < length; i++) { int right = i; for (int left = i + 1; left < length; left++) { while (right + 1 < length && nums[right + 1] < nums[i] + nums[left]) { right++; } res += Math.max(right - left, 0); } } return res; } }