跳至主要內容

0611. 有效三角形的个数

ITCharge大约 2 分钟

0611. 有效三角形的个数open in new window

  • 标签:贪心、数组、双指针、二分查找、排序
  • 难度:中等

题目链接

题目大意

描述:给定一个包含非负整数的数组 numsnums,其中 nums[i]nums[i] 表示第 ii 条边的边长。

要求:统计数组中可以组成三角形三条边的三元组个数。

说明

  • 1nums.length10001 \le nums.length \le 1000
  • 0nums[i]10000 \le nums[i] \le 1000

示例

  • 示例 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:对撞指针

构成三角形的条件为:任意两边和大于第三边,或者任意两边差小于第三边。只要满足这两个条件之一就可以构成三角形。以任意两边和大于第三边为例,如果用 aabbcc 来表示的话,应该同时满足 a+b>ca + b > ca+c>ba + c > bb+c>ab + c > a。如果我们将三条边升序排序,假设 abca \le b \le c,则如果满足 a+b>ca + b > c,则 a+c>ba + c > bb+c>ab + c > a 一定成立。

所以我们可以先对 numsnums 进行排序。然后固定最大边 ii,利用对撞指针 leftleftrightright 查找较小的两条边。然后判断是否构成三角形并统计三元组个数。

为了避免重复计算和漏解,要严格保证三条边的序号关系为:left<right<ileft < right < i。具体做法如下:

  • 对数组从小到大排序,使用 ansans 记录三元组个数。
  • i=2i = 2 开始遍历数组的每一条边,ii 作为最大边。
  • 使用双指针 leftleftrightrightleftleft 指向 00rightright 指向 i1i - 1
    • 如果 nums[left]+nums[right]nums[i]nums[left] + nums[right] \le nums[i],说明第一条边太短了,可以增加第一条边长度,所以将 leftleft 右移,即 left += 1
    • 如果 nums[left]+nums[right]>nums[i]nums[left] + nums[right] > nums[i],说明可以构成三角形,并且第二条边固定为 rightright 边的话,第一条边可以在 [left,right1][left, right - 1] 中任意选择。所以三元组个数要加上 rightleftright - left。即 ans += (right - left)
  • 直到 left==rightleft == right 跳出循环,输出三元组个数 ansans

思路 1:代码

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        size = len(nums)
        ans = 0

        for i in range(2, size):
            left = 0
            right = i - 1
            while left < right:
                if nums[left] + nums[right] <= nums[i]:
                    left += 1
                else:
                    ans += (right - left)
                    right -= 1
        return ans

思路 1:复杂度分析

  • 时间复杂度O(n2)O(n^2),其中 nn 为数组中的元素个数。
  • 空间复杂度O(logn)O(\log n),排序需要 logn\log n 的栈空间。