Problem:
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
Note:
- The length of the given array won’t exceed 1000.
- The integers in the given array are in the range of [0, 1000].
Idea:
Greedy
Time Complexity:
O(n^2)
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: int triangleNumber(vector<int>& nums) { if (nums.size() < 3) return 0; std::sort(nums.rbegin(), nums.rend()); int n = nums.size(); int ans = 0; for (int c = 0; c < n-2; ++c) { int b = c + 1; int a = n - 1; while (b < a) { if (nums[a] + nums[b] > nums[c]) { ans += (a - b); ++b; } else { --a; } } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment