Given an array consists of non-negative integers, your task is to count 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: [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

This problem is very similar to 3-Sum, in 3-Sum, we can use three pointers (i, j, k and i < j < k) to solve the problem in O(n^2) time for a sorted array, the way we do in 3-Sum is that we first lock pointer i and then scan j and k, if nums[j] + nums[k] is too large, k–, otherwise j++, once we complete the scan, increase pointer i and repeat.

For this problem, once we sort the input array nums, the key to solve the problem is that given nums[k], count the combination of i and j where nums[i] + nums[j] > nums[k] (so that they can form a triangle). If nums[i] + nums[j] is larger than nums[k], we know that there will be j – i combination.

Let’s take the following array for example, let’s mark the three pointers:

```
i j k
[3, 19, 22, 24, 35, 82, 84]
```

because 3 + 82 > 84 and the numbers between 3 and 82 are always larger than 3, so we can quickly tell that there will be j – i combination which can form the triangle, and they are:

```
3, 82, 84
19, 82, 84
22, 82, 84
24, 82, 84
35, 82, 84
```

Now let’s lock k and point to 35:

```
i j k
[3, 19, 22, 24, 35, 82, 84]
```

because 3 + 24 < 35, if we move j to the left, the sum will become even smaller, so we have to move pointer i to the next number 19, and now we found that 19 + 24 > 35, and we don’t need to scan 22, we know that 22 must be ok!

1 public static int triangleNumber(int[] A) { 2 Arrays.sort(A); 3 int count = 0, n = A.length; 4 for (int i=n-1;i>=2;i--) { 5 int l = 0, r = i-1; 6 while (l < r) { 7 if (A[l] + A[r] > A[i]) { 8 count += r-l; 9 r--; 10 } 11 else l++; 12 } 13 } 14 return count; 15 }

https://leetcode.com/problems/valid-triangle-number/discuss/128135/A-similar-O(n2)-solution-to-3-Sum