[LeetCode] 611. Valid Triangle Number

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.

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

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

有效三角形的个数。

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

这道题的思路有点类似 3sum。因为是要找能组成三角形的三条边，所以一定要满足 a + b > c，其中两条边的和要大于第三条边。所以思路是先 sort input数组（a < b < c），然后从数组末端开始扫描，把当前遍历到的数字当做三角形的最长的边 c，然后再用 two pointer 找另外两条边 a 和 b。找的方式是，如果 a + b > c 则说明当 c 是最长边的时候，abc 这个组合是满足题意的，res += b - a。为什么 a - b 之间的所有组合都能累加进去是因为这里我们考虑的是 b 和 c 不变的情况下，把 a 右移的情况，此时需要 b 左移；如果 a + b < c 的话，那么只能是 a 右移，因为长度不够。

时间O(n^2) - worst case

空间O(1)

Java实现

 1 class Solution {
 2     public int triangleNumber(int[] nums) {
 3         int res = 0;
 4         Arrays.sort(nums);
 5         for (int i = nums.length - 1; i >= 0; i--) {
 6             int left = 0;
 7             int right = i - 1;
 8             while (left < right) {
 9                 if (nums[left] + nums[right] > nums[i]) {
10                     res += right - left;
11                     right--;
12                 } else {
13                     left++;
14                 }
15             }
16         }
17         return res;
18     }
19 }