611. Valid Triangle Number

time: O(n^2)

space: O(1)

/*
sort first

small + small > larger

start from 2, want larger be th fix pointer target

how to get count?
t is the target(larger side)
l r t
2 2 3 4
cnt = 1 - 0 = 1

l   r t
2 2 3 4
cnt = 2 - 0 = 2

l r   t
2 2 3 4 
dont count

1+2 = 3

[4,2,3,4]
sort
2 3 4 4


C(3, 4) = 4

same element:

[1, 1, 1, 1]

if consider each 1 are different in actually, this problem dont need ingnore duplicate
               t
1', 1'', 1''', 1
cnt = 1

l          r   t
1', 1'', 1''', 1
cnt = 2

l   r          t
1', 1'', 1''', 1
cnt = 1

1+2+1 = 4
*/
class Solution {
    public int triangleNumber(int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;    
        }
        
        int cnt = 0;
        Arrays.sort(nums);
        for (int i = 2; i < nums.length; i++) {
            cnt += getCnt(nums, i);
        }
        return cnt;
    }
    private int getCnt(int[] nums, int targetIdx) {
        int cnt = 0;
        
        int left = 0;
        int right = targetIdx - 1;
        
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > nums[targetIdx]) {
                cnt += right - left;
                right--;
            } else {
                left++;
            }
        }
        return cnt;
    }
}

T: O(n^2)
S: O(1)

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

/**
T: O(n^2)
S: O(1)

ll r i
2 3 4 4
count 1
234a

l   r i
2 3 4 4
count 2
means l to r all can use -> 24 or 34 (r is fixed), l+r 
because we sort it, if 2+4 is > i , then 3+4 most > i
34a4b
24a4b


l r   i
2 3 4 4
234b
count 1

 */
```