侧边栏壁纸
博主头像
mkdir700博主等级

思考人生意义的码农

  • 累计撰写 31 篇文章
  • 累计创建 43 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

611. 有效三角形的个数

mkdir700
2022-08-28 / 0 评论 / 0 点赞 / 59 阅读 / 1,567 字 / 正在检测是否收录...

描述

给定一个包含非负整数的数组 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

标签
#数组 #双指针 #排序 #二分查找 #贪心


题解

0x01 排序 + 双指针

  1. 先将数组升序排序;
  2. 逆序遍历,遍历到的每一位,用其前一位的值(红色块,left 所在位置)与最左位置的值(默认为0 号位,橙色块,right 所在位置)相加之和与当前遍历到的值做比较(蓝色块)
    1. 如果两者之和大于当前值,则可以构成三角形,那么 right - left 的值,就是这个区间内的所有可能性,这个不难理解,因为这个数组是升序的嘛。一个最小值+一个最大值都已经满足了条件,那么最小值后面直到最大值之前的值肯定也满足条件。
      1. 上一步尝试的是 最小值+最大值,所以可以左移 right 以减小两者之和,直到两者之和不满足条件
    2. 如果两者之后小于或等于当前值,则不能构成三角形,不能构成的原因就是两者之和太小了,right 所在位置已经是最大值了,所以只能让 left 所在位置的值变大,那么整体的和才会变大,也就是让 left 向右移动。

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

0x02 排序 + 二分查找

在上一个方法中,我们是固定一个数,然后确定另外两个数的区间。
这个方法则是,先固定两个数,再通过二分查找另一个数的最大值。

我们有一个用于比较的值,就是 nums[i] + nums[j],必须要一个数大于这两者之和,才可以组成三角形。

接下来就使用二分查找从后面这个区间内,找出一个满足大于两者之和这个条件的最大值。 这个最大值默认就是 nums[len(nums) - 1],即这个数组的最后一位。

这个区间是 [j+1, len(nums)-1],这个还是蛮清楚的吧,

二分查找内的条件判断如下:

  1. 如果中间值(nums[mid])小于两者之和(nums[i] + nums[j]),则说明满足三角形的构造条件,暂存下 mid 的值,为了确保 mid 之后仍有符合条件的值,左边界右移(mid + 1)
  2. 否者中间值大于或等于两者之和,不满足条件,右边界左移(mid-1)。
  3. 本次循环的结果就是,最大值位置 - 第二值的位置,这就是本次遍历的满足三角形的构造的数量,如图,找到的最大值是 10,从第二个值(2)的位置到最大值的位置,就是本次遍历的符合条件的个数。
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        nl = len(nums)
        ans = 0
        for i in range(nl):
            for j in range(i + 1, nl):
                left, right, k = j + 1, nl - 1, j
                while left <= right:
                    # nums[i] + nums[j]
                    # 匹配到的值必须大于这个和,才能构成三角形
                    mid = (left + right) // 2
                    if nums[i] + nums[j] > nums[mid]:
                        k = mid
                        left = mid + 1
                    else:
                        right = mid - 1
                ans += k - j
        return ans
0

评论区