611. 有效三角形的个数 - 力扣（LeetCode）
思路
1.使用双指针的思想，利用单调性进行快速找到符合条件的三元组的个数
2.情况A:nums[left] + nums[right] > nums[i]这说明当前的 left 是满足条件的最小下限。既然最小的都能过，那么 left 右侧到 right-1 之间的所有元素作为第一条边都必然成立。动作： 计数并执行 right–。理由： 我们已经穷举了以当前 right 为第二条边的所有可能，下一步需要减小 right 来检测更小的边界。
3.情况B：nums[left] + nums[right] <= nums[i]这说明当前的 left 太小了，即便加上当前最大的 right 也够不到三角形的门槛。动作： 执行 left++。理由： 既然当前的 right 已经给出了最大支援还是失败，那么当前的 left 绝不可能出现在任何以 i 为最大边的组合中，必须舍弃。
代码
package doublepointer;
import java.util.Arrays;
//给定一个包含非负整数的数组 nums ，
//返回其中可以组成三角形三条边的三元组个数。
//输入: nums = [2,2,3,4]
//输出: 3
//解释:有效的组合是:
// 2,3,4 (使用第一个 2)
// 2,3,4 (使用第二个 2)
// 2,2,3
public class TriangleNumber {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
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;
}
public static void main(String[] args) {
int[] nums={2,2,3,4};
TriangleNumber triangleNumber=new TriangleNumber();
System.out.println(triangleNumber.triangleNumber(nums));
}
}
1 个帖子 - 1 位参与者
来源: linux.do查看原文