611. 有效三角形的個數

思路

有效三角形的三個邊，需要滿足「兩邊之和大於第三邊」。
那麼我們先固定一個邊，枚舉其他兩邊，當滿足條件時，就算做有效的組合。
直接暴力做的時間複雜度會是 $O(n^3)$，而 $n$ 最大是1000，會超時，勢必要找個方法優化。

三條邊分別為 $a, b, c$，只需要確保 $\max(a,b,c)$ 是否小於其他兩數之和就行，最大值能帶比較小的那兩個數字飛。

因此能排序數組，固定取第一個邊 $x$，此時位於它左邊的數字都比較小，
找到一對數值和大於它，就計入答案中。
這樣稍微優化後的複雜度還是 $O(n^3)$，不過會壓線通過。

可以很明顯地觀察到，現在第一條邊取 $\text{nums[k]}$，
假如最小的兩個邊 $\text{nums[0] + nums[1]}$ 都能大過它，
那麼在 $0\sim{k}$ 任取三條邊都會滿足條件，方法數增加 $C^{k + 1}_3 = \frac{(k + 1)k(k - 1)}{6}$。
同樣的，假如最大的兩條邊 $\text{nums[k - 1] + nums[k - 2]}$ 都要小於 $\text{nums[k]}$，
那麼任取三條邊都不會滿足條件。

最後，用雙指針找到合法的兩邊數值，假如找到，那麼在固定b的條件下，左指針的位置left 到 right - 1 的邊都是合法的。

程式碼

class Solution
{
public:
    int triangleNumber(vector<int>& nums) {
        ranges::sort(nums);
        const int n = nums.size();
        int res = 0;
        for(int k = n - 1; k > 1; --k) {
            if(nums[0] + nums[1] > nums[k]) {
                res += (k + 1) * k * (k - 1) / 6;
                break;
            }
            if(nums[k - 2] + nums[k - 1] <= nums[k]) {
                continue;
            }
            int left = 0, right = k - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[k]) {
                    res += right - left;
                    --right;
                }
                else {
                    ++left;
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(1)$