• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 611. Valid Triangle Number

10个月前 (03-13) 61次浏览

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