• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送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


程序员灯塔
转载请注明原文链接:611. Valid Triangle Number
喜欢 (0)