题目描述

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

样例

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意

• 数组长度不超过 1000。
• 数组里整数的范围为 [0, 1000]。

算法1

(枚举+二分) $O(n^2 \log n)$

1. 将整个数组从小到大排序。
2. 在排序后的数组上，从前向后枚举三角形的两个较短的边 nums[i] 和 nums[j]，较短的边不能为 0，然后求这两个边的和记为 t。
3. 在数组中二分查找第一个大于等于 t 的位置 p（若不存在 p = n），p - j - 1 就是这两个边所能构成的三角形的个数。

时间复杂度

• 数组排序时间复杂度为 $O(n \log n)$，枚举的时间复杂度为 $O(n^2)$，每次需要 $O(\log n)$的时间寻找位置，故总时间复杂度为 $O(n^2 \log n)$。

C++ 代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++)
            if (nums[i] > 0)
                for (int j = i + 1; j < n; j++) {
                    int t = nums[i] + nums[j];
                    ans += lower_bound(nums.begin(), nums.end(), t) - nums.begin() - j - 1;
                }
        return ans;
    }
};

算法2

(枚举+线性扫描) $O(n^2)$

1. 将整个数组从小到大排序。
2. 在排序后的数组上，从前向后枚举三角形的两个较短的边 nums[i] 和 nums[j]，较短的边不能为 0。
3. 在确定了最短的边 nums[i] 后，令 k = i + 1，然后再枚举次短的边 nums[j] 后，不断向后更新 k，使得 nums[i] + nums[j] <= nums[k]。由于 nums[j] 单调递增，故 k 也会单调递增。最终对于每次枚举的 nums[j]，累计的答案个数就是 k - j - 1。

时间复杂度

• 数组排序时间复杂度为 $O(n \log n)$，枚举最短边的时间复杂度为 $O(n)$。确定了最短边之后，每个值最多只会遍历两次，故总时间复杂度为 $O(n^2)$。

C++ 代码

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