problem

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

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

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

solution

/**
find all a <= b <= c   make triangles, so a < c - b
iterate all c , iterate all b , than binary seach a 
time complexity O(n^2 log n)
 */
class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        int ret = 0;
        Arrays.sort(nums);
        for (int i = n-1; i >= 0; i--) {
            int c = nums[i];
            for (int k = i - 1; k >=1; k--) {
                int b = nums[k];
                // find the smallest index j 
                // satisfy nums[j] =  a  > c - b = target;
                int j = binarySearch(nums, 0, k-1, c - b);
                ret += (k - j);
            }
        }
        return ret;
    }

    public int binarySearch(int[] arr,int left, int right, int t) {
        while(left <= right) {
            int mid = left + (right - left)/2;
            if (arr[mid] > t) {
                right = mid - 1;
            } else {
                left = mid +1;
            }
        }
        return left;
    }
}

/**
two pointer
 */
class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        int ret = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1, k = j; j < n-1 && k < n; j++) {
                // find the max k , nums[k] < a + b
                if (k < j) {
                    k = j;
                }
                while(k+1 < n && nums[k+1] < nums[i] + nums[j]) {
                    k++;
                }
                ret += (k-j);
            }
        }
        return ret;
    }

}