力扣 611.有效三角形的个数

题目介绍

解法

有效三角形：两个短边和大于最长边

思路：将数组从小到大进行排序，外层循环从后向前进行遍历作为最长边，内层循环用相向双指针 l 和 r 分别代表两个短边，通过比较两个短边和 和最长边的大小关系来移动相向双指针。

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length - 1 , res = 0;
        for(int i = n ; i > 1; i--){
            int l = 0, r = i - 1;
            // 和2824题 统计小于目标的小标对数目 解法一样
            while(l < r){
                int sum = nums[l] + nums[r];
                if(sum > nums[i]){
                    res = res + r - l;
                    r--;
                }else{
                    l++;
                }
            }
        }
        return res;
    }
}