有效三角形的个数(二分、双指针)

传送门

　　https://leetcode-cn.com/problems/valid-triangle-number/

题意

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

思路1

　　对于三角形的三条边需要满足两边之和大于第三边，我们将这个条件转换为两个较小边大于第三边。所以我们可以先对该数组进行一个排序，然后从数组左端开始枚举i和j，这就是我们的两个较小边。然后在数组右端二分查找第三边统计答案即可。时间复杂度为(nnlogn)

AC代码1

import java.util.Arrays;

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int res = 0;
        for (int i = 0; i < len; i++) {
            int x = nums[i];
            for (int j = i + 1; j < len; j++) {
                int y = nums[j], tar = x + y, k = j;
                int l = j + 1, r = len - 1;
                while (l <= r) {
                    int m = l + (r - l) / 2;
                    if(nums[m] < tar){
                        k = m;
                        l = m + 1;
                    }else{
                        r = m - 1;
                    }
                }
                res += k - j;
            }
        }
        return res;
    }
}

思路2

　　对于思路1中的i、j、k，我们可以发现随着j的不断右移，nums[i]+nums[j]是不断递增的，所以此时k也就有了右移动的空间。我们就可以将 j和 k 看成两个同向（递增）移动的指针，右移j指针的时候不断维护k能到达的最右断点，此时k - j就是当前移动j指针带来的收益。需要注意的是因为数组有0的存在，所以可能会出现k在j左边的情况，故要对收益k - j 为负的时候进行一个处理。

AC代码2

import java.util.Arrays;

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int res = 0;
        for (int i = 0; i < len; i++) {
            int k = i;
            for(int j = i + 1; j < len; j++){
                while(k + 1 < len && nums[i] + nums[j] > nums[k+1]){
                    k++;
                }
                res += Math.max(k - j,0);
            }
        }
        return res;
    }
}
/*
 2 2 3 4 5 7
 0 1 2 3 4 5

 0 0 3 3 5 7
 0 1 2 3 4 5
 */