class Solution {
public:
int triangleNumber(vector<int>& nums) {
}
};
611. 有效三角形的个数
给定一个包含非负整数的数组 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相似题目
原站题解
python3 解法, 执行用时: 2472 ms, 内存消耗: 15 MB, 提交时间: 2022-12-10 13:00:15
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
nums.sort()
ans = 0
for i in range(n):
k = i
for j in range(i + 1, n):
while k + 1 < n and nums[k + 1] < nums[i] + nums[j]:
k += 1
ans += max(k - j, 0)
return ans
javascript 解法, 执行用时: 112 ms, 内存消耗: 42.9 MB, 提交时间: 2022-12-10 13:00:02
/**
* @param {number[]} nums
* @return {number}
*/
var triangleNumber = function(nums) {
const n = nums.length;
nums.sort((a, b) => a - b);
let ans = 0;
for (let i = 0; i < n; ++i) {
let k = i;
for (let j = i + 1; j < n; ++j) {
while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
++k;
}
ans += Math.max(k - j, 0);
}
}
return ans;
};
golang 解法, 执行用时: 36 ms, 内存消耗: 3 MB, 提交时间: 2022-12-10 12:59:41
func triangleNumber(nums []int) (ans int) {
n := len(nums)
sort.Ints(nums)
for i, v := range nums {
k := i
for j := i + 1; j < n; j++ {
for k+1 < n && nums[k+1] < v+nums[j] {
k++
}
ans += max(k-j, 0)
}
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
java 解法, 执行用时: 28 ms, 内存消耗: 41.3 MB, 提交时间: 2022-12-10 12:59:16
// 双指针
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;
}
}
golang 解法, 执行用时: 212 ms, 内存消耗: 3 MB, 提交时间: 2022-12-10 12:58:05
func triangleNumber(nums []int) (ans int) {
sort.Ints(nums)
for i, v := range nums {
for j := i + 1; j < len(nums); j++ {
ans += sort.SearchInts(nums[j+1:], v+nums[j])
}
}
return
}
javascript 解法, 执行用时: 452 ms, 内存消耗: 43.2 MB, 提交时间: 2022-12-10 12:57:52
/**
* @param {number[]} nums
* @return {number}
*/
var triangleNumber = function(nums) {
const n = nums.length;
nums.sort((a, b) => a - b);
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
let left = j + 1, right = n - 1, k = j;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < nums[i] + nums[j]) {
k = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
ans += k - j;
}
}
return ans;
};
python3 解法, 执行用时: 8252 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-10 12:50:16
'''
排序+二分查找
'''
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
nums.sort()
ans = 0
for i in range(n):
for j in range(i + 1, n):
left, right, k = j + 1, n - 1, j
while left <= right:
mid = (left + right) // 2
if nums[mid] < nums[i] + nums[j]:
k = mid
left = mid + 1
else:
right = mid - 1
ans += k - j
return ans