【C++算法】6.双指针_有效三角形的个数-C++ 算法代码:

解法一(暴力求解)(会超时)O(nlogn+n3)

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1. 排序
        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 0;
        // 2. 从小到大枚举所有的三元组
        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])
                        ret++;
                } 
            }
        }
        return ret;
    }
};

解法二(排序 + 双指针)O(n2)

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        // 1. 优化,排序一下数组
        sort(nums.begin(), nums.end());
        // 2. 利用双指针解决问题
        int ret = 0, n = nums.size();
        for(int i = n - 1; i >= 2; i--) // 先固定最大的数,从后往前固定
        {
            // 利用双指针快速统计符合要求的三元组的个数
            int left = 0, right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i]){
                    ret += right - left;
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return ret;
    }
};

上一篇:算法训练营打卡Day18


下一篇:学什么