Leetcode 611有效三角形数
来源：1-5 大厂面试为什么总考算法？
甲骨文_0001
2022-04-25
老师，611题我是用了3重for循环，再依据三角形两边和大于第三边的性质来得到最后结果:
然后，我看了老师github的leetcode仓库，611题解法，是二分查找思路，我没有想明白:)
https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0611-Valid-Triangle-Number/cpp-0611/main.cpp, 老师，指点下哈~~~，另外我想问下，体系课的KMP小节大概什么时候可以出来，十分期待了~~~~~~~ _
写回答
1回答
-
liuyubobobo
2022-04-26
一旦确定了三角形的两条边 a 和 b，那么三角形的第三条边一定大于两边之差（的绝对值），小于两边之和。
所以只需要遍历 a 和 b，然后看给出的边中，有多少条边的大小在 |a - b| 和 a + b 之间即可。所以可以在初始对所有边排序，然后使用二分找到第一个大于 |a - b| 的边的索引和最后一个小于 a + b 的边的索引，用这两个索引直接就能求出中间有多少条边。复杂度优化成为了 O(n^2 logn) 的。
==========
小宇宙马上就入托了，我就能录课了。很快了，很快了，黎明前的胜利.... = =
抱歉。
继续加油！：）
112022-04-26
相似问题