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

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

解题思路

解题思路

判断三个数能否组成三角形的关键在于：任意两边之和大于第三边。对于三条边 a、b、c，如果 a ≤ b ≤ c，那么只需要验证 a + b > c 即可（因为其他两个条件自动满足）。

方法一：排序 + 双指针（推荐）

  1. 排序：首先对数组排序，便于后续处理
  2. 固定最大边：从右往左遍历，将当前元素作为最大边 c
  3. 双指针查找：对于固定的最大边 c，使用双指针在其左侧寻找满足条件的 a 和 b
    • 左指针 left = 0，右指针 right = i - 1
    • 如果 nums[left] + nums[right] > nums[i]，说明 [left, right-1] 范围内的所有元素都可以与 nums[right] 组成有效三角形，答案增加 (right - left)，然后 right–
    • 否则说明 nums[left] 太小，left++

这种方法的优势在于：当 nums[left] + nums[right] > nums[i] 时，nums[left+1]、nums[left+2]…nums[right-1] 与 nums[right] 的组合都满足条件，可以一次性计算多个结果。

方法二：暴力枚举

三重循环枚举所有可能的三元组，时间复杂度 O(n³)，适用于数据量较小的情况。

方法三：排序 + 二分查找

固定两条边，使用二分查找第三条边的范围，时间复杂度 O(n² log n)。

代码实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int count = 0;
        int n = nums.size();
        
        for (int i = n - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return count;
    }
};

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

public class Solution {
    public int TriangleNumber(int[] nums) {
        Array.Sort(nums);
        int count = 0;
        int n = nums.Length;
        
        for (int i = n - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return count;
    }
}

var triangleNumber = function(nums) {
    nums.sort((a, b) => a - b);
    let count = 0;
    const n = nums.length;
    
    for (let i = n - 1; i >= 2; i--) {
        let left = 0, right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                count += right - left;
                right--;
            } else {
                left++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
排序 + 双指针O(n²)O(1)
暴力枚举O(n³)O(1)
排序 + 二分查找O(n² log n)O(1)

推荐使用排序 + 双指针的方法，时间复杂度最优为 O(n²)。

相关题目