每日一题:有效三角形的个数

2025/9/26 每日一题算法二分双指针

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

题目很简洁，就是求能够构成三角形三条边的三元组个数。自然地，我们就可以先从暴力法去思考。怎么做？显然三重循环枚举每一个数，再通过三角形的构成条件进行计数，就获得了答案。三角形需要最小的两边之和大于第三边。可以对数组排个序，就可以直接固定。于是就有了下面的代码，但是居然通过了~~（太暴力了~~

public class Solution {
    public int TriangleNumber(int[] nums) {
        int ans = 0;
        int n = nums.Length;

        if(n < 3) return ans;

        Array.Sort(nums);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                for(int k = j + 1; k < n; k++){
                    if(nums[i] + nums[j] > nums[k]) ans++;
                }
            }
        }

        return ans;
    }
}

很明显这个解法是不够看的，因为时间复杂度太高，达到O(n^3)

那么怎么优化？

观察目前的代码，会发现k那层的循环是明显可以优化的。前两层确定了最小的两条边，剩下的就是变成了找小于这两边之和的数的个数，然后加起来就是答案。关键在于找。有什么小于O(n)的查找？自然而然就该想到算法守门员，二分。可以把找k的那个数，通过二分查找，快速找到，然后计数。这样的时间复杂度是O(n^2logn)，参考代码如下

public class Solution {
    public int TriangleNumber(int[] nums) {
        int ans = 0;
        int n = nums.Length;

        if(n<3) return ans;

        Array.Sort(nums);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                int sum = nums[i] + nums[j];
                int l = j, r = n;
                while(l + 1 < r){
                    int mid = l + r >> 1;
                    if(nums[mid] >= sum){
                        r = mid;
                    }else{
                        l = mid;
                    }
                }
                ans += r - j - 1; 
            }
        }

        return ans;
    }
}

二分查找的是第一个大于等于最小两边和的数，然后减去前面的索引就是这次的个数。

那么还有办法优化吗？继续观察结构，nums[i]+nums[j]>nums[k]，现在我们是固定两条短边找第三边。那我们是不是还可以反过来，固定最长边，找前面两条短边的个数？只要这个查找的过程小于O(nlogn)，那么就能继续优化一个级别。

已知最长边，怎么快速计算两条短边的个数？是不是这两个短边按照升序时，一左一右，最边界的两个能够满足三角形条件的话，中间的所有都是满足的。边界相减就是存在的个数。那就很明显了，一左一右双指针，在锁定最长边的情况下，只要这两个边符合构成三角形就能进行一次计数。那么只要遍历一次最长边，使用一个最长边去还要遍历一次，最极端情况下就是要去到最右边，即还需要遍历一次。那么时间复杂度就是O(n^2)。

重新梳理一遍，避免绕晕。枚举最长边，维护左右指针。那么这个指针要从哪开始？自然是最左边和最右边，然后两个指针往中间缩进。参考代码如下

public class Solution {
    public int TriangleNumber(int[] nums) {
        int ans = 0;
        int n = nums.Length;

        if(n<3) return ans;

        Array.Sort(nums);
        for(int i = 0; i < n; i++){
            int l = 0, r = i - 1;
            while(l < r){
                if(nums[l] + nums[r] > nums[i]){
                    ans += r - l;
                    r--;
                }else{
                    l++;
                }
            }
        }

        return ans;
    }
}

枚举的i是最长边，因此，短边的最右边理论上就是最长边的前一位。因为这里我们是做了升序操作的。然后就是左右指针往中间缩进，当满足条件的时候，进行一次计数。因为我们是要两边之和大于第三边，所以不满足的时候，左边需要右移，不断增加。当满足了，计数之后，右指针左移，减少看看还有没有其他左指针符合条件。当左右指针相逢时，这个最长边的情况下的所有两个短边的情况都计算完了。

总结优化思路

暴力 O(n³)：三重循环，直接枚举所有可能情况
二分 O(n² log n)：枚举两最小边 + 二分找最长边
双指针 O(n²)：枚举最长边，双指针维护两最小边

LOADING

每日一题:有效三角形的个数