给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。

解1

暴力求解，时间复杂度n^3

  public int triangleNumber(int[] nums) {
        int len = nums.length,res = 0;
        if(len<3)
            return 0;
        Arrays.sort(nums);
        int a,b,c;
        for(int i=0;i<len-2;i++){
            a = nums[i];
            for(int j=i+1;j<len-1;j++){
                b = nums[j];
                for(int k = j+1;k<len;k++){
                    c = nums[k];
                    if(a+b>c)
                        res++;
                    else
                        break;
                }
            }
        }
        return res;
    }

解2

时间复杂度n^2。从后往前遍历数组，每次遍历时对该位置的左边的数组使用双指针的思想，从头和尾做一次遍历。

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