611. Valid Triangle Number

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

My Solutions:

三角形形成的条件是两边之和大于第三边。先sort array，从最大的一个数开始，如果最小数+次大数

• 大于第三边（最大数），说明从最小数到次大数之间的数，都可以和最大数形成三角形。

  • 比如[2,2,2,3,4]，第一个2(index=l)和3(index=r)可以和4形成三角形，则可以形成三角形的个数是r - l。更新完结果后，向左移动次大数。

• 没有大于第三边（最大数），需要向右移动最小数。

public int triangleNumber(int[] nums) {
    if (nums == null || nums.length < 3) return 0;
    int count = 0;
    Arrays.sort(nums);

    for (int i = nums.length - 1; i >= 2; i--) {
        int l = 0, r = i - 1;
        while (l < r) {
            if (nums[l] + nums[r] > nums[i]) {
                count += r - l;
                r--;
            } else {
                l++;
            }
        }
    }
    return count;