双指针算法实战：有效三角形与多数之和 | 极客日志

C++算法

双指针算法实战：有效三角形与多数之和

双指针算法适用于有序数组的查找问题。通过排序后固定一端，利用左右指针相向移动寻找满足条件的组合。文章涵盖有效三角形个数统计、两数之和、三数之和及四数之和四个经典案例。重点讲解去重策略与边界条件处理，相比暴力枚举显著降低时间复杂度。

灵魂摆渡发布于 2026/3/210 浏览

双指针算法实战：有效三角形与多数之和

1、有效三角形的个数

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

解题思路：

暴力解法：枚举所有的三条边，判断它们是否可以组成三角形，记录有效三角形的个数。不过 n^3 的时间复杂度会超出时间限制！

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int len=nums.size(),count=0;
        for(int a=0;a<len-2;a++) {
            for(int b=a+1;b<len-1;b++) {
                for(int c=b+1;c<len;c++) {
                    if(nums[a]+nums[b]>nums[c] &&nums[a]+nums[c]>nums[b] &&nums[b]+nums[c]>nums[a]) count++;
                }
            }
        }
        return count;
    }
};

更优解法：先将数组排序，因为判断三个数是否可以构成三角形只需要比较较小两边之和是否大于第三边即可。
排序后，nums[len-1]的位置就是最大值，我们先用 right_idx 固定一端，right 固定在 right_idx 左侧，left 固定在起点。
判断 nums[left]+nums[right] 是否大于 nums[right_idx]。
- a. 如果小于，left++
- b. 如果大于，count+=(right-left)。固定 right_idx 和 right 两边后，left 是 right 之后最小的一边。如果最小的一边加上 right 都大于 right_idx，那其后的边一定可以构成三角形。所以我们就没有必要进行无意义的枚举。

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int right_idx=nums.size()-1,count=0;
        //排序
        sort(nums.begin(),nums.end());
        //固定枚举 right_idx
        while(right_idx>=2) {
            //固定枚举 right
            int right=right_idx-1;
            int left=0;
            while(left<right) {
                if(nums[left]+nums[right]>nums[right_idx]) {
                    count+=(right-left);
                    right--;
                } else left++;
            }
            right_idx--;
        }
        return count;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left=0,right=price.size()-1;
        while(left<right) {
            if(price[left]+price[right]<target) left++;
            else if(price[left]+price[right]>target) right--;
            else {
                return {price[left],price[right]};
            }
        }
        return {-1,-1};
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());//排序
        int len=nums.size();
        for(int k=len-1;k>=2;) {
            if(nums[k]<0) break;//小优化
            int left=0,right=k-1;
            while(left<right) {
                if(nums[left]+nums[right]<-nums[k]) left++;
                else if(nums[left]+nums[right]>-nums[k]) right--;
                else {
                    ret.push_back({nums[left++],nums[right--],nums[k]});
                    //去重
                    while(left<right&&nums[left]==nums[left-1]) left++;
                    while(left<right&&nums[right]==nums[right+1]) right--;
                }
            }
            //去重
            k--;
            while(k>=2&&nums[k]==nums[k+1]) k--;
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int len=nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        for(int d=len-1;d>=3;) {
            if(target<0&&nums[0]>=0) break;//小优化
            //三数之和逻辑
            for(int c=d-1;c>=2;) {
                long long tmp=(long long)target-nums[c]-nums[d];
                int left=0;
                int right=c-1;
                while(left<right) {
                    if(nums[left]+nums[right]<tmp) left++;
                    else if(nums[left]+nums[right]>tmp) right--;
                    else {
                        ret.push_back({nums[left++],nums[right--],nums[c],nums[d]});
                        //left,right去重
                        while(left<right&&nums[left]==nums[left-1]) left++;
                        while(left<right&&nums[right]==nums[right+1]) right--;
                    }
                }
                //c去重
                c--;
                while(c>=2&&nums[c]==nums[c+1]) c--;
            }
            //d去重
            d--;
            while(d>=3&&nums[d]==nums[d+1]) d--;
        }
        return ret;
    }
};