Valid Triangle Number Problem
Description
LeetCode Problem 611.
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:
1
2
3
4
5
6
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:
1
2
Input: nums = [4,2,3,4]
Output: 4
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int res = 0, n = nums.size();
sort(nums.begin(), nums.end());
for (int i = n-1; i >= 0; i--) {
int lo = 0, hi = i-1;
while (lo < hi) {
if (nums[lo] + nums[hi] > nums[i]) {
res += hi - lo;
hi--;
}
else
lo++;
}
}
return res;
}
};