LeetCode 611. 有效三角形的个数

---

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例1：

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

解题思路

1.暴力

​ 这道题要求枚举符合条件的三元组，最简单的方法是通过三层循环直接枚举所有的组合，对三边都进行 a+b<c && a+c<b && b+c<a 的判断，累加求出个数。

2.排序+二分

​ 首先我们对数组进行排序，对于已排序数组，即三元组a < b < c，当且仅当 a + b > c时符合条件，因此我们可以通过两层循环固定a,b，对于c在有序区间中找到小于a+b的最大值，则(b,c]中的元素个数即为当前a,b对应的解个数，累加即可。

​ 时间复杂度为 $n^2log(n)$

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

3.排序+双指针

​ 依然首先对数组排序，我们考虑a + b > c的条件，我们可以先固定最长边c，通过双指针来寻找a,b。一个关键点在于反向遍历c，每一个c对应的left和right指针，left=0，right=k-1。
​ 如果nums[left] + nums[right] > c,则[left, right]区间的所有数符合条件，right左移；
​ 如果nums[left] + nums[right] <= c,则left右移，直到大于c。
​ 最后left于right碰撞，即已经找完当前c对应的所有解。

​ 时间复杂度为 $n^2$

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