牛客232639题解析：双指针+排序算法高效求解三角形数量（附代码详解）

一、题目解读

牛客232639题要求计算一个整数数组中能够组成有效三角形的三边组合数量。根据三角形不等式，三边需满足任意两边之和大于第三边。例如，数组[3, 4, 5, 6]可组成两个有效三角形（[3, 4, 5]和[3, 5, 6]）。题目核心在于如何高效遍历所有组合并判断其有效性，避免暴力枚举带来的O(n^3)时间复杂度。

二、解题思路

采用“排序+双指针”策略，将问题转化为固定最长边后，通过双指针动态调整短边组合：

1. 预处理：对数组进行升序排序，确保最长边位于末尾，便于后续固定。

2. 外层循环：从末尾开始遍历，依次固定每个元素作为最长边（nums[k]）。

3. 内层双指针：使用双指针i和j（i=0,j=k-1）分别从左右两端逼近，动态判断三角形条件。

4. 关键优化：若当前短边和（nums[i] + nums[j]）大于最长边，则存在多个可行组合（因左侧[i,j)区间所有数均可与nums[j]组成三角形），直接累加组合数；否则，向右移动短边指针寻找更大值。

通过该策略，将时间复杂度优化至O(n^2)，结合排序的O(nlogn)，总复杂度为O(n^2)，但实际运行效率显著提升。

三、解题步骤

1. 排序数组：使用sort函数对nums进行升序排列，为后续双指针操作奠定基础。

2. 外层循环：从右至左遍历数组（k从n-1到2），依次固定最长边nums[k]。

3. 双指针初始化：设置左指针i=0，右指针j=k-1，形成初始短边范围。

4. 动态判断：

    若nums[i] + nums[j] > nums[k]，说明当前组合有效，且存在j-i个可行组合（因左侧所有数均满足条件），累加计数并右移j指针。

    若不满足条件，则左移i指针寻找更大短边。

5. 循环终止：当i≥j时，当前最长边无法组成三角形，跳出内层循环。

6. 返回统计结果：外层循环结束后，累积计数即为有效三角形总数。

四、代码与注释

class Solution {
public:
    int validTriangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 升序排序，确保最长边位于末尾
        
        int n = nums.size();
        int count = 0;                  // 计数器初始化
        
        // 外层循环：固定最长边nums[k]
        for (int k = n - 1; k >= 2; --k) {  // 从末尾开始遍历（k从n-1到2）
            int i = 0, j = k - 1;        // 双指针初始化：左i=0，右j=k-1
            
            while (i < j) {              // 双指针移动条件
                // 满足三角形条件：短边和大于最长边
                if (nums[i] + nums[j] > nums[k]) {
                    count += j - i;      // 统计当前可行组合数（右侧有j-i个可选短边）
                    j--;                 // 右指针左移，尝试更小的第三边
                } else {
                    i++;                 // 左指针右移，寻找更大的第二边
                }
            }
        }
        return count;                    // 返回累计结果
    }
};

注释解析：代码通过排序打破原始顺序依赖，利用双指针的动态移动精准统计可行组合，避免冗余计算。外层循环从长边入手，内层通过条件判断直接跳过无效组合，大幅提升效率。

五、总结

本解法巧妙结合排序与双指针技术，将三角形判定问题转化为有序序列中的区间计数问题。通过固定最长边、动态调整短边组合的策略，有效避免了暴力枚举的指数级复杂度。尽管时间复杂度为O(n^2)，但实际性能优于传统方法，尤其在数据规模较大时表现突出。该算法思路对处理有序序列中的组合问题具有重要参考价值，适用于面试或竞赛中的优化场景。