乐趣区

关于python:内含干货611-有效三角形的个数

jiezi

题目地址(611. 无效三角形的个数)

https://leetcode-cn.com/probl…

题目形容

给定一个蕴含非负整数的数组，你的工作是统计其中能够组成三角形三条边的三元组个数。示例 1:

输出: [2,2,3,4]
输入: 3
解释:
无效的组合是:
2,3,4 (应用第一个 2)
2,3,4 (应用第二个 2)
2,2,3
留神:

数组长度不超过 1000。数组里整数的范畴为 [0, 1000]。

前置常识

  • 排序
  • 双指针
  • 二分法
  • 三角形边的关系

暴力法（超时）

思路

首先要有一个数学前提：如果三条线段中任意两条的和都大于第三边，那么这三条线段能够组成一个三角形。即给定三个线段 a，b，c，如果满足 a + b > c and a + c > b and b + c > a，则线段 a，b，c 能够形成三角形，否则不能够。

力扣中有一些题目是须要一些数学前提的，不过这些数学前提都比较简单，个别不会超过高中数学常识，并且也不会特地简单。个别都是小学初中常识即可。

如果你在面试中碰到不晓得的数学前提，能够寻求面试官提醒试试。

关键点解析

  • 三角形边的关系
  • 三层循环确定三个线段

代码

代码反对: Python

class Solution:
    def is_triangle(self, a, b, c):
        if a == 0 or b == 0 or c == 0: return False
        if a + b > c and a + c > b and b + c > a: return True
        return False
    def triangleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if self.is_triangle(nums[i], nums[j], nums[k]): ans += 1

        return ans

复杂度剖析

  • 工夫复杂度：$O(N ^ 3)$，其中 N 为 数组长度。
  • 空间复杂度：$O(1)$

优化的暴力法

思路

暴力法的工夫复杂度为 $O(N ^ 3)$，其中 $N$ 最大为 1000。一般来说，$O(N ^ 3)$ 的算法在数据量 <= 500 是能够 AC 的。1000 的数量级则须要思考 $O(N ^ 2)$ 或者更好的解法。

OK，到这里了。我给大家一个干货。应该是其余博主不太会提的。起因可能是他们不晓得，也可能是他们感觉太小儿科不须要说。

  1. 因为后面我依据数据规模揣测到到理解法的复杂度区间是 $N ^ 2$, $N ^ 2 * logN$，不可能是 $N$（WHY？）。
  2. 升高工夫复杂度的办法次要有：空间换工夫 和 排序换工夫 （咱们个别都是应用基于比拟的排序办法）。而 排序换工夫 仅仅在总体复杂度大于 $O(NlogN)$ 才实用（起因不必多说了吧？）。

这里因为总体的工夫复杂度是 $O(N ^ 3)$，因而我天然想到了 排序换工夫。当咱们对 nums 进行一次排序之后，我发现：

  • is_triangle 函数有一些判断是有效的
    def is_triangle(self, a, b, c):
        if a == 0 or b == 0 or c == 0: return False
        # a + c > b 和  b + c > a 是有效的判断，因为恒成立
        if a + b > c and a + c > b and b + c > a: return True
        return False
  • 因而咱们的指标变为找到 a + b > c 即可，因而第三层循环是能够提前退出的。
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        k = j + 1
        while k < n and num[i] + nums[j] > nums[k]:
            k += 1
        ans += k - j - 1
  • 这也仅仅是减枝而已，复杂度没有变动。通过进一步察看，发现 k 没有必要每次都从 j + 1 开始。而是从上次找到的 k 值开始就行。起因很简略，当 nums[i] + nums[j] > nums[k] 时，咱们想要找到下一个满足 nums[i] + nums[j] > nums[k] 的 新的 k 值，因为进行了排序，因而这个 k 必定比之前的大（枯燥递增性），因而上一个 k 值之前的数都是有效的，能够跳过。
for i in range(n - 2):
    k = i + 2
    for j in range(i + 1, n - 1):
        while k < n and nums[i] + nums[j] > nums[k]:
            k += 1
        ans += k - j - 1

因为 K 不会后退，因而最内层循环总共最多执行 N 次，因而总的工夫复杂度为 $O(N ^ 2)$。

这个复杂度剖析有点像枯燥栈，大家能够联合起来了解。

关键点剖析

  • 排序

代码

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

复杂度剖析

  • 工夫复杂度：$O(N ^ 2)$
  • 空间复杂度：取决于排序算法

更多题解能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858…。目前曾经 30K star 啦。

关注公众号力扣加加，致力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你辨认套路，高效刷题。

退出移动版