What is the best approach for Valid Triangle Number?

Sort the array and use either two pointers or binary search to count all triplets satisfying the triangle inequality.

Can zeros or duplicates affect the triangle count?

Yes, zeros cannot form triangles and duplicates must be considered carefully to avoid double counting valid triplets.

What is the time complexity of the optimal solution?

Sorting takes O(n log n) and counting with two pointers or binary search gives O(n^2) or O(n^2 log n).

Why is binary search useful in this problem?

It finds the largest valid third side efficiently, reducing the need for nested loops and avoiding O(n^3) brute-force checks.

How does GhostInterview handle the triangle inequality pattern?

It guides through sorting, pointer selection, and index calculation to ensure all valid triplets are counted correctly with minimal mistakes.

#611

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

有效三角形的个数

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

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

题目描述

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

lightbulb

解题思路

方法一：排序 + 二分查找

一个有效三角形需要满足：任意两边之和大于第三边。即：

$a + b \gt c \tag{1}$

$a + c \gt b \tag{2}$

$b + c \gt a \tag{3}$

如果我们将边按从小到大顺序排列，即 $a \leq b \leq c$ ，那么显然 (2)(3) 成立，我们只需要确保 (1) 也成立，就可以形成一个有效三角形。

我们在 $[0, n - 3]$ 范围内枚举 i，在 $[i + 1, n - 2]$ 范围内枚举 j，在 $[j + 1, n - 1]$ 范围内进行二分查找，找出第一个大于等于 $nums[i] + nums[j]$ 的下标 left，那么在 $[j + 1, left - 1]$ 范围内的 k 满足条件，将其累加到结果 $\textit{ans}$ 。

时间复杂度 $O(n^2\log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting the array before counting triplets
question_mark
Using two pointers or binary search for the third side
question_mark
Avoiding O(n^3) brute-force enumeration

warning

常见陷阱

外企场景

error
Not sorting the array first, causing incorrect triangle checks
error
Ignoring duplicate numbers leading to miscounted triplets
error
Miscalculating the range of the third side or using incorrect indices

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count triangles with perimeter below a given threshold
arrow_right_alt
Find all unique triplets instead of counting them
arrow_right_alt
Allow negative numbers and determine valid triangle counts accordingly

help

常见问题

外企场景

继续练习

#826 安排工作以达到最大收益 #581 最短无序连续子数组 #658 找到 K 个最接近的元素