611. 有效三角形的个数

双指针

1. 首先对数组排序。
2. 固定最长的一条边，运用双指针扫描
3. 如果 nums[l] + nums[r] > nums[i]，同时说明 nums[l + 1] + nums[r] > nums[i], ..., nums[r - 1] + nums[r] > nums[i]，满足的条件的有 r - l 种，r 左移进入下一轮。
4. 如果 nums[l] + nums[r] <= nums[i]，l 右移进入下一轮。
5. 枚举结束后，总和就是答案。
6. 时间复杂度为 O(n^2)

class Solution {
    public int triangleNumber(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length;
        int res = 0;
        for(int i = n-1 ; i >= 0 ; i-- ){
            int sum = nums[i];
            int left = 0;
            int right = i-1;
            while(left < right){
                if(nums[left] + nums[right] > sum){
                    res += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return res;

    }
}