题目

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

解题思路

核心思想是利用排序来简化判断条件，并结合双指针或二分查找来高效地计数。

解法一：暴力法（会超时）

最直观的思路是使用三层循环，枚举所有的三元组 (nums[i], nums[j], nums[k])，然后检查它们是否满足上述三个条件。

时间复杂度: $O(N^3)$，其中 N 是数组的长度。
空间复杂度: $O(1)$。

对于 N <= 1000 的数据规模，$1000^3=10^9$，这个计算量太大了，一定会超时。因此我们需要优化。

解法二：排序 + 二分查找 (优化)

优化的关键在于排序。首先，我们将 nums 数组升序排列。

排序后，如果我们选取的三条边 a, b, c 满足 a <= b <= c，那么 a+c > b 和 b+c > a 这两个条件就必然成立了。我们只需要检查最短的两边之和是否大于最长的那条边，即 a + b > c。

这样，问题就转化成了：

在一个排序后的数组中，找到所有满足 nums[i] + nums[j] > nums[k] 的三元组 (i, j, k)，其中 i < j < k。

思路如下：

对数组 nums 进行升序排序。
使用两层循环，固定 i 和 j（即三角形的两条较短边 a 和 b）。
对于固定的 nums[i] 和 nums[j]，我们需要找到有多少个 nums[k]（其中 k > j）满足 nums[k] < nums[i] + nums[j]。
由于数组是排序的，我们可以在 nums 的 [j+1, n-1] 这个区间内，通过二分查找来高效地找到第一个不满足条件（即 nums[k] >= nums[i] + nums[j]）的元素位置。假设这个位置是 k_bound，那么从 j+1 到 k_bound - 1 之间的所有元素都满足条件。
这些满足条件的元素个数就是 k_bound - (j + 1)。将这个数量累加到总数中。

时间复杂度: $O(N^2 \log N)$。外层两层循环是 $O(N^2)$，内层的二分查找是 $O(\log N)$。
空间复杂度: $O(\log N)$ 或 $O(N)$，取决于排序算法使用的额外空间。

解法三：排序 + 双指针 (最优解)

这是本题的最佳解法，可以进一步将时间复杂度优化到 $O(N^2)$。

这个思路是反过来想：我们先固定最长的那条边 c，然后去找有几对 (a, b) 能跟它组成三角形。

思路如下：

对数组 nums 进行升序排序。
从后向前遍历数组，固定 k 作为最长边的索引（c = nums[k]）。k 的范围从 n-1 到 2。
对于每个固定的 k，我们在它前面的子数组 [0, k-1] 中寻找满足 nums[left] + nums[right] > nums[k] 的数对。
我们使用双指针 left 和 right，分别指向子数组的开头（left = 0）和结尾（right = k-1）。
移动指针：
- 如果 nums[left] + nums[right] > nums[k]：
  - 这说明 (nums[left], nums[right], nums[k]) 可以构成三角形。
  - 更重要的是，由于 nums[left] 是当前最小的可能值，那么保持 nums[right] 不变，将 left 换成 left+1, left+2, ..., right-1 中的任意一个 i，nums[i] + nums[right] 也必然大于 nums[k]。
  - 因此，以 nums[right] 为第二条边，第一条边可以是 nums[left], nums[left+1], ..., nums[right-1]。这里共有 right - left 种组合。
  - 我们将这 right - left 种组合全部累加到结果中。
  - 然后，我们尝试让 right 指针左移（right--），去寻找一个更小的第二条边。
- 如果 nums[left] + nums[right] <= nums[k]：
  - 说明 nums[left] 和 nums[right] 的和太小了。
  - 为了让和变大，我们需要增大较小的那个数，所以 left 指针右移（left++）。

时间复杂度: $O(N^2)$。外层 k 的循环是 $O(N)$，内层的双指针 left 和 right 最多也移动 $O(N)$ 次。总共是 $O(N^2)$。再加上排序的 $O(N \log N)$，最终时间复杂度是 $O(N^2)$。
空间复杂度: $O(\log N)$ 或 $O(N)$，取决于排序算法。

具体代码

排序 + 二分查找

通过先排序，我们将判断条件简化为 a + b > c。然后我们固定两条较短的边 a 和 b，再用二分查找来高效地计算出有多少条可能的第三边 c。

class Solution {
public:
    int triangleNumber(std::vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return 0;
        }

        std::sort(nums.begin(), nums.end());
        
        int count = 0;
        // 固定两条较短的边 nums[i] 和 nums[j]
        for (int i = 0; i < n - 2; ++i) {
            // 题目说明是非负整数，如果 nums[i] 为 0，无法构成三角形
            if (nums[i] == 0) continue; 
            for (int j = i + 1; j < n - 1; ++j) {
                int sum = nums[i] + nums[j];
                
                // 在区间 [j+1, n-1] 中寻找第一个大于等于 sum 的元素
                // std::lower_bound 返回一个迭代器，指向第一个不小于给定值的元素
                auto it = std::lower_bound(nums.begin() + j + 1, nums.end(), sum);
                
                // 从 j+1 的位置到 it 之前的位置，都是有效的第三边
                count += std::distance(nums.begin() + j + 1, it);
            }
        }
        return count;
    }
};

排序 + 双指针 (最优解)

先对数组排序，然后从后向前遍历，固定最长的一条边 c。之后，在 c 前面的区间内使用双指针 left 和 right，寻找所有满足 a + b > c 的数对 (a, b)。

class Solution {
public:
    int triangleNumber(std::vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return 0;
        }

        std::sort(nums.begin(), nums.end());
        
        int count = 0;
        // 从后往前遍历，固定最长的一条边 nums[k]
        for (int k = n - 1; k >= 2; --k) {
            int left = 0;
            int right = k - 1;
            
            while (left < right) {
                if (nums[left] + nums[right] > nums[k]) {
                    // 如果 nums[left] + nums[right] > nums[k]，
                    // 那么 right 指针左边的所有元素（从 left 到 right-1）
                    // 与 nums[right] 相加也一定大于 nums[k]。
                    // 因此，我们找到了 right - left 个有效的组合。
                    count += (right - left);
                    right--; // 尝试缩小第二条边，继续寻找
                } else {
                    // 如果和不够大，我们需要增大较小的数，即 left 指针右移
                    left++;
                }
            }
        }
        return count;
    }
};

611. 有效三角形的个数

beautifulremi

题目