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.
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 [
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 [
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!