0611：有效三角形的个数（★）

2016-09-02 约 294 字预计阅读 1 分钟次阅读

力扣第 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 <= 1000
0 <= nums[i] <= 1000

相似问题：

分析

只要 a、b、c 满足 0<a<=b<=c<a+b，即可组成三角形
因此将 nums 排序，并固定最长边为 nums[k]，即转为求两数之和大于某值的个数，可以用双指针解决

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        res = 0
        for k in range(2,n):
            i,j = 0,k-1
            while i<j:
                if nums[i]+nums[j]<=nums[k]:
                    i += 1
                else:
                    res += j-i
                    j -= 1
        return res

556 ms

目录

0611：有效三角形的个数（★）

题目

分析

解答