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.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 1000
	0 &lt;= nums[i] &lt;= 1000


class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int count =0;
        for(int k = n-1; k>=2; k--)
        {
            int i = 0;
            int j = k-1;
            while(i < j)
            {
                int sum = nums[i] +nums[j];
                if(sum > nums[k])
                {
                    count += j-i;
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }
        return count;
    }
}
class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int count =0;
        for(int k = n-1; k>=2; k--)
        {
            int i = 0;
            int j = k-1;
            while(i < j)
            {
                int sum = nums[i] +nums[j];
                if(sum > nums[k])
                {
                    count += j-i;
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }
        return count;
    }
}
class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int count =0;
        for(int k = n-1; k>=2; k--)
        {
            int i = 0;
            int j = k-1;
            while(i < j)
            {
                int sum = nums[i] +nums[j];
                if(sum > nums[k])
                {
                    count += j-i;
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }
        return count;
    }
}
class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int count =0;
        for(int k = n-1; k>=2; k--)
        {
            int i = 0;
            int j = k-1;
            while(i < j)
            {
                int sum = nums[i] +nums[j];
                if(sum > nums[k])
                {
                    count += j-i;
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }
        return count;
    }
}
Valid Triangle Number