LeetCode 611. 有效三角形的个数

Categories:

Tags:

题目描述
思路分析
1. 解法一：排序 + 双指针（推荐）
相似题目

题目描述

✅ 611. 有效三角形的个数

思路分析

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

核心思路：

三角形成立的条件是任意两边之和大于第三边。对于排序后的数组，只需验证最小两边之和 > 最大边。

先对数组升序排序，然后从最大边 k 开始向左枚举，用双指针 i（左）和 j（右，初始为 k-1）在 [0, k-1] 范围内寻找满足 nums[i] + nums[j] > nums[k] 的对数。

当 nums[i] + nums[j] > nums[k] 时，由于数组有序，[i, j-1] 范围内的所有左指针与 j 组合均满足条件，共 j - i 对，将结果加上 j - i 后将 j 左移。

当 nums[i] + nums[j] <= nums[k] 时，说明左指针太小，将 i 右移增大。

复杂度分析：

时间复杂度：O(n²)，其中 n 表示数组长度，排序 O(n log n)，双重循环 O(n²) 主导

空间复杂度：O(log n)，其中 log n 为排序使用的递归栈空间

class Solution {
    public int triangleNumber(int[] nums) {
        // 升序排序，使得对于固定最大边，只需验证最小两边之和 > 最大边
        Arrays.sort(nums);
        int res = 0;
        int n = nums.length;

        // 枚举最大边 k，从右向左遍历
        for (int k = n - 1; k >= 2; k--) {
            int i = 0, j = k - 1;
            // 双指针在 [0, k-1] 范围内寻找满足条件的对数
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    // [i, j-1] 与 j 的组合均满足条件，共 j - i 对
                    res += j - i;
                    j--;
                } else {
                    // 两数之和不足，左指针右移增大
                    i++;
                }
            }
        }

        return res;
    }
}

func triangleNumber(nums []int) int {
	// 升序排序，使得对于固定最大边，只需验证最小两边之和 > 最大边
	sort.Ints(nums)
	res := 0
	n := len(nums)

	// 枚举最大边 k，从右向左遍历
	for k := n - 1; k >= 2; k-- {
		i, j := 0, k-1
		// 双指针在 [0, k-1] 范围内寻找满足条件的对数
		for i < j {
			if nums[i]+nums[j] > nums[k] {
				// [i, j-1] 与 j 的组合均满足条件，共 j - i 对
				res += j - i
				j--
			} else {
				// 两数之和不足，左指针右移增大
				i++
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
15. 三数之和	中等	排序 + 双指针、枚举固定值
16. 最接近的三数之和	中等	排序 + 双指针、最优值更新
18. 四数之和	中等	排序 + 双指针、多层枚举
259. 较小的三数之和	中等	排序 + 双指针、计数
1099. 小于 K 的两数之和	简单	排序 + 双指针
167. 两数之和 II - 输入有序数组	中等	双指针
11. 盛最多水的容器	中等	双指针、贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/03455614