611. 有效三角形的个数 Medium

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

解题思路

输入：一个非负整数数组 nums

输出：返回可以组成三角形的组合个数

本题属于 排序 + 相向双指针 问题。

三角形三边必须满足 任意两边之和 > 第三边 的条件

假设排序后数组是 nums[0] <= nums[1] <= ... <= nums[n-1]，那我们要找的三元组 (i, j, k) 必须满足：

nums[i] + nums[j] > nums[k]

我们可以排序之后固定最长边 k，然后从前面两个指针 i 和 j 找满足条件的组合。。

只要满足条件，则说明 [i, j] 之间所有组合都满足，直接 count += j - i，之后移动 j -= 1 减少边长再去找

如果不满足条件就需要移动 i += 1 增大边长

代码实现

python

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        # 首先将数组排序，方便后续使用双指针
        nums.sort()
        n = len(nums)
        count = 0

        # 枚举每个可能作为最长边的索引 k，从后往前遍历
        for k in range(n - 1, -1, -1):
            i, j = 0, k - 1  # i 从头开始，j 从 k 前一位开始

            # 双指针判断是否满足三角形条件：nums[i] + nums[j] > nums[k]
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    # 若满足条件，则从 i 到 j 之间的所有 i 都满足条件，共有 j - i 个组合
                    count += j - i
                    j -= 1  # 缩小右边界
                else:
                    i += 1  # 增加左边界，以尝试更大的 nums[i]
        
        # 返回所有满足条件的三元组数量
        return count

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
    nums.sort((a, b) => a - b);
    let count = 0;

    for (let k = nums.length - 1; k > 0; k--) {
        let i = 0;
        let j = k - 1;

        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
    }

    return count;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

611 国际版

611 中文版