题目描述
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:
输入: nums = [4,2,3,4]
输出: 4
提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
解法
方法一：排序 + 二分查找
一个有效三角形需要满足：任意两边之和大于第三边。即：a + b > c①, a + c > b②, b + c > a③。
如果我们将边按从小到大顺序排列，即 a < b < c，那么显然 ②③ 成立，我们只需要确保 ① 也成立，就可以形成一个有效三角形。
我们在 [0, n - 3] 范围内枚举 i，在 [i + 1, n - 2] 范围内枚举 j，在 [j + 1, n - 1] 范围内进行二分查找，找出第一个大于等于 nums[i] + nums[j] 的下标 left，那么在 [j + 1, left - 1] 范围内的 k 满足条件，将其累加到结果 ans。
时间复杂度：$O(n^2\log n)$。
| class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort()
ans, n = 0, len(nums)
for i in range(n - 2):
for j in range(i + 1, n - 1):
k = bisect_left(nums, nums[i] + nums[j], lo=j + 1) - 1
ans += k - j
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int res = 0;
for (int i = n - 1; i >= 2; --i) {
int l = 0, r = i - 1;
while (l < r) {
if (nums[l] + nums[r] > nums[i]) {
res += r - l;
--r;
} else {
++l;
}
}
}
return res;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0, n = nums.size();
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
int k = lower_bound(nums.begin() + j + 1, nums.end(), nums[i] + nums[j]) - nums.begin() - 1;
ans += k - j;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func triangleNumber(nums []int) int {
sort.Ints(nums)
ans := 0
for i, n := 0, len(nums); i < n-2; i++ {
for j := i + 1; j < n-1; j++ {
left, right := j+1, n
for left < right {
mid := (left + right) >> 1
if nums[mid] >= nums[i]+nums[j] {
right = mid
} else {
left = mid + 1
}
}
ans += left - j - 1
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function triangleNumber(nums: number[]): number {
nums.sort((a, b) => a - b);
let n = nums.length;
let ans = 0;
for (let i = n - 1; i >= 2; i--) {
let left = 0,
right = i - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
ans += right - left;
right--;
} else {
left++;
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | impl Solution {
pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
nums.sort();
let n = nums.len();
let mut res = 0;
for i in (2..n).rev() {
let mut left = 0;
let mut right = i - 1;
while left < right {
if nums[left] + nums[right] > nums[i] {
res += right - left;
right -= 1;
} else {
left += 1;
}
}
}
res as i32
}
}
|
方法二