153、有效三角形的个数

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

示例 1:

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

数组长度不超过1000。
数组里整数的范围为 [0, 1000]。

先排序然后用指针

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

进行优化

注意：如果l和r以及i可以组成，那么l+1…r-1都可以组成，因此不需要一个个累加
代码：

class Solution {
    public int triangleNumber(int[] nums) {
        if (nums == null || nums.length <= 2) return 0;
        Arrays.sort(nums);
        int res = 0;
        int i = nums.length - 1;
        while (i >= 2){
            int min = nums[i];
            int l = 0;
            int r = i - 1;
            while (l < r){
                if (nums[l] + nums[r] <= min){
                    l++;
                } else {
                    res += r - l;
                    r--;
                }
            }
            i--;
        }
        
        return res;
    }
}