【优选算法】有效三角形的个数

链接：611. 有效三角形的个数 - 力扣（LeetCode）

算法原理：

数学知识：给三个数，判断是否能够构成三角形

优化：先对整个数组排序

方法一：暴力枚举

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                for (int k = j - 1; k >= 0; k--) {
                    if (nums[j] + nums[k] > nums[i]) ans++;
                }
            }
        }
        return ans;
    }
}

复杂度分析：

• 时间复杂度：排序时间复杂度为 O(nlogn)；三层遍历找所有三元祖的复杂度为 O(n^3)。整体复杂度为 O(n^3)
• 空间复杂度：O(logn)

方法二：利用单调性，使用双指针算法来解决问题 

1.先固定最大的数

2.在最大的数的左区间内，使用双指针算法，快速统计出符合要求的三元组的个数

class Solution {
    public int triangleNumber(int[] nums) {
        //1.优化，排序
        Arrays.sort(nums);
        //2.利用双指针解决问题
        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;
    }
}