每日一题 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

题解

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums); //对数组排序 增加条件int ans = 0;//依次枚举每个元素 定义双指针left和right //如果nums[left] + nums[right] <= nums[i]则向右移动left //nums[left]和nums[right]是小的两个数for (int i = 0; i < nums.length; i++) {for (int right = i - 1, left = 0; left < right; right--) {while (left < right && nums[left] + nums[right] <= nums[i]) {left++;}//nums[left] nums[right] nums[i] 符合答案//第一个元素换成nums[left + 1]...nums[right - 1] 依然符合答案//所以个数为right-1-left+1=right-leftans += right - left;}}return ans;}
}