Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【leetcode刷题】:双指针篇(有效三角形的个数、和为s的两个数)

【leetcode刷题】:双指针篇(有效三角形的个数、和为s的两个数)

作者头像
爱喝兽奶的熊孩子
发布于 2025-01-10 00:20:09
发布于 2025-01-10 00:20:09
6800
代码可运行
举报
文章被收录于专栏:C语言基础C语言基础
运行总次数:0
代码可运行
一、有效三角形的个数
题目解析

有效三角形的个数【点击跳转】

题目意思很好理解:就是在一堆非负整数的数组里,随机选三个数进行搭配,然后统计这个数组中任意三个数能组成三角形的组合个数。

注意: 判断任意三个数是否能组成三角形的条件是 任意 两个数相加大于第三个数。

【示例一】: 输入: nums = [2,2,3,4] 输出: 3 四个数选三个数总共有四种情况

情况一:2 2 3 (任意两个数大于第三个数)满足题意 情况二:2 2 4 (2 + 2等于四)不满足题意 情况三:2 3 4 (任意两个数大于第三个数)满足题意 情况四:2 3 4 (任意两个数大于第三个数)满足题意

可以组成三个三角形,所以输出为3

【示例二】: 输入: nums = [4,2,3,4] 输出: 4 四个数选三个数总共有四种情况

情况一:4 2 3 (任意两个数大于第三个数)满足题意 情况二:4 2 4 (任意两个数大于第三个数)满足题意 情况三:4 3 4 (任意两个数大于第三个数)满足题意 情况四:2 3 4 (任意两个数大于第三个数)满足题意

可以组成四个三角形,所以输出为4

算法原理

解法一:暴力枚举(超时) 将所有的情况全部枚举出来,然后统计符合题意的情况。 暴力枚举代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 暴力枚举
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int count = 0;
        // 固定第一个数
        for(int i = 0; i < nums.size(); i++)
        {
            // 固定第二个数
            for(int j = i + 1; j < nums.size(); j++)
            {
                // 固定第三个数
                for(int k = j + 1; k < nums.size(); k++)
                {
                    if((nums[i] + nums[j] > nums[k]) && (nums[i] + nums[k] > nums[j]) && (nums[j] + nums[k] > nums[i]))
                        count++;
                }
            }
        }
        return count;
    }
};

解法二:排序 + 双指针 首先根据题目的意思是数组里的元素都是大于等于零的,这里我们就可以利用组成三角形的一个特性:

假设三个数a、b、c,最大数是c,那么:

  • 1、a + c > b
  • 2、b + c > a
  • 3、a + b > c 这是判断是否能构成三角形的条件

其实第一种和第二种情况可以合并成一种情况,因为c是最大的那个数,一个最大的数加一个大于零的数,其结果一定是大于另外一个数的

知道了这个特性,我们的算法就有了优化的空间。

我们可以先给数组里的元素排个序,先固定一个最大的数,然后利用双指针算法结合上面讲的特性来优化算法:

根据上面的图可以看到,最大的数是13,然后会有下面这几种情况:

  • 情况一nums[left] + nums[right] > c
  • 情况二nums[left] + nums[right] <= c 小于和等于属于同一种情况,即不能构成三角形

根据单调性,假设是情况一,因为left往右的数都是比left大的数,left加上right已经大于最大的数了,那么一个大于left的数加上right,那必定是大于最大的数c的,所以left往右就没必要计算了,因为left与right这个区间再加上最大数构成的三个数一定是能构成三角形的,能构成三角形的个数就是right - left,接下来的操作就是要right往左移,然后继续判断

假设是情况二,left加上right是小于最大值c的,那么right往左的数与left相加也一定是小于最大数c,所以接下来的操作是要left往右移,然后继续判断。

最后双指针判断结束后,只需要更新最大值(最大值往左移),然后重新利用双指针进行判断。

代码编写

C++代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 排序
        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 0;
        // 固定最大数
        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;
    }
};

C语言代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 比较函数
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int triangleNumber(int* nums, int numsSize) {
    // 排序
    qsort(nums, numsSize, sizeof(int), cmpfunc);
    int ret = 0;
    // 固定最大数
    for(int i = numsSize - 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;
}

Python代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        # 排序
        nums.sort()
        ret = 0
        # 固定最大数
        for i in range(len(nums) - 1, 1, -1):
            left, right = 0, i - 1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    ret += right - left
                    right -= 1
                else:
                    left += 1
        return ret
二、和为s的两个数
题目解析

和为s的两个数【点击跳转】

题目的大意就是给你一个递增的数组,然后找到两个数相加等于目标值,然后返回这两个数,返回的这两个数顺序随意。

算法原理

解法一:暴力枚举(超时) 直接两层for循环将所有的可能全部枚举出来,然后找到两个数相加等于目标值的两个数,直接返回。

暴力枚举C++代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        // 固定第一个数
        for(int i = 0; i < price.size(); i++)
        {
            // 固定第二个数
            for(int j = i + 1; j < price.size(); j++)
            {
                if(price[i] + price[j] == target)
                    // 这里是隐式类型转换,可以转换成vector<int>类型
                    return {price[i], price[j]};
            }
        }
        // 满足力扣的要求,这里的值可随意返回
        return {-1, -1};
    }
};

解法二:双指针 在暴力枚举的时候我们忽略了一个很重要的因素,那就是这个数组里的元素是单调递增的,只要是单调递增的数组,我们就可以大胆的利用双指针算法来解决问题。

1、第一种情况:sum = price[left] + price[right] > target 如果sum大于我们的目标值target,由于数组是单调递增的,price[left]已经是最小的值了,price[right]是数组中最大的那个数。一个最小的值加上一个最大的值最后大于目标值,而且left往后的值都是大于left的(数组递增),所以我们的操作就只要让right往左移就可以了。

2、第二种情况:sum = price[left] + price[right] < target 相加后的结果小于目标值target,说明left小了(right左边的值都是小于right的),所以我们的操作只需要让left向右移动即可。

3、第三种情况:sum = price[left] + price[right] == target 相加后的结果是等于目标值target,满足题目要求,直接结果即可。

相比于解法一的暴力解法,利用数组的单调递增的双指针解法效率更高,我们可以分析一下两种解法的时间复杂度对比。

\text{暴力解法:} O(N^2) \\ \text{双指针:} O(N)

可以看到时间复杂度直接优化了一个量级,说明我们的算法是比较优秀的算法了。

代码编写

C++代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int n = price.size();
        // 定义左右双指针
        int left = 0, right = n - 1;
        while(left < right)
        {
            // sum > target
            if(price[left] + price[right] > target)
                right--;
            // sum < target
            else if(price[left] + price[right] < target)
                left++;
            // sum == target
            else
                return {price[left], price[right]};
        }
        return {-1, -1};
    }
};

C语言代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* price, int priceSize, int target, int* returnSize) {
    // 定义左右双指针
    int left = 0, right = priceSize - 1;
    *returnSize = 2;  // 输出型参数
    int *ret = (int*)malloc(*returnSize * sizeof(int));
    while(left < right)
    {
        // sum > target
        if(price[left] + price[right] > target)
            right--;
        // sum < target
        else if(price[left] + price[right] < target)
            left++;
        // sum == target
        else
        {
            ret[0] = price[left], ret[1] = price[right];
            return ret;
        }
    }
    // 释放空间
    free(ret);
    ret = NULL;
    return NULL;
}

Python代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def twoSum(self, price: List[int], target: int) -> List[int]:
        # 定义左右双指针
        left, right = 0, len(price) - 1
        while left < right:
            # sum > target
            if price[left] + price[right] > target:
                right -= 1
            # sum < target
            elif price[left] + price[right] < target:
                left += 1
            # sum == target
            else:
                return [price[left], price[right]]
        return [-1, -1]
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
​LeetCode刷题实战611:有效三角形的个数
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2022/06/07
2480
每日一练【有效三角形的个数】
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。
用户11316056
2024/10/16
740
每日一练【有效三角形的个数】
优先算法 —— 双指针系列 - 有效三角形的个数
https://leetcode.cn/problems/valid-triangle-number/description/
迷迭所归处
2024/12/24
680
优先算法 —— 双指针系列 - 有效三角形的个数
【优选算法】有效三角形的个数(双指针算法)
三层for循环枚举出所有三元组,判读每组是否能构成三角形,会超时,但是我们可以再优化一下:先对数组进行排序,只需判断三元组中最小的两个数是否大于第三个数即可,省略有一些不必要的判断。
云边有个稻草人
2025/01/03
780
【优选算法】有效三角形的个数(双指针算法)
双指针算法的妙用:提高代码效率的秘密(3)
小编在昨日讲述了关于双指针算法的两个题目,今日继续分享两个题目的解析,我相信,我只要坚持每天啥刷题,算法能力终究会提高的,下面废话不多说,开始进入今天的代码时间。 正文:
用户11295429
2024/11/15
1340
双指针算法的妙用:提高代码效率的秘密(3)
【优选算法】5----有效三角形个数
这道题的题目算是最近几道算法题里面题目最短的,但是单单看题目的话,我就只知道有一个数
用户11456817
2025/01/24
570
【优选算法】5----有效三角形个数
有效三角形个数问题
想必大家看到这道题首先一定想的就是三次循环嵌套,然后再加上判断三角形(任意两边都大于第三步)来完成此操作。伪代码:
羑悻的小杀马特.
2025/01/23
730
有效三角形个数问题
算法思想总结:双指针算法
该题的重要信息:1、不要在超过该数组的长度的位置写入元素(就是不要越界)2、就地修改(就是不能创建新数组)。3、不返回任何东西。
小陈在拼命
2024/03/16
1520
算法思想总结:双指针算法
每日一题:LeetCode-611. 有效三角形的个数
   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,拾取经验,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️
用户11029129
2024/06/04
880
每日一题:LeetCode-611. 有效三角形的个数
【优选算法】——Leetcode——611. 有效三角形的个数
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。
小李很执着
2024/06/15
1520
【优选算法】——Leetcode——611. 有效三角形的个数
【算法一周目】双指针(2)
题目链接:611. 有效三角形的个数 题目描述:给定一个包含非负整数的数组nums,返回其中可以组成三角形三条边的三元组个数。
HZzzzzLu
2024/11/26
910
【算法一周目】双指针(2)
LeetCode 611. 有效三角形的个数(双指针)
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-triangle-number 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Michael阿明
2020/07/13
4110
LeetCode 611. 有效三角形的个数(双指针)
初识算法 · 双指针(2)
本文介绍两个题目,盛最多水的容器和有效三角形的个数,对应的Leetcode的题目链接为:
_lazy
2024/10/16
970
初识算法 · 双指针(2)
【优先算法】专题——双指针
题目分析:题目说不要超过数组长度其实就是告诉我们不要越界,题目还告诉我们不能创建额外数组让我们就地修改原数组,我们不需要返回任何内容。
用户11375356
2024/11/25
1550
【优先算法】专题——双指针
有效三角形的个数
当c>a,c>b时,我们只需要判断一个条件a+b>c是否满足就可以了,满足就能构成一个三角形。
用户11162265
2025/03/28
550
有效三角形的个数
611. 有效三角形的个数
给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 class Solution { public int triangleNumber(int[] nums) { /** 双指针: 找到最大值(不断--) 如果两个数之和>最大
编程张无忌
2021/06/21
2620
【c++算法篇】双指针(下)
我们知道,三角形的满足条件是任意的两边之和大于第三边,但是如果我们已经判断了较小的两个边大于第三边,就不需要再进行剩下两组的判断,所以我们先进行排序,再进行枚举:
用户11029103
2024/05/08
1800
【c++算法篇】双指针(下)
【优选算法】Pointer-Slice:双指针的算法切片(下)
一般针对三元的变量,优先想到的是三层 for 循环暴力枚举所有的组合,此时的时间复杂度为O(n³),明显是超时了。争取遍历一遍就能找出所有组合,那么就要减少无效的枚举
DARLING Zero two
2024/12/26
770
【优选算法】Pointer-Slice:双指针的算法切片(下)
【优选算法篇】双指针的华丽探戈:深入C++算法殿堂的优雅追寻
题目链接:611. 有效三角形的个数 题目描述:给定一个包含非负整数的数组 nums,返回其中可以组成三角形三条边的三元组个数。
半截诗
2024/10/15
1300
【优选算法篇】双指针的华丽探戈:深入C++算法殿堂的优雅追寻
双指针算法详解
维护三个区间 0~dest为非0元素 , dest + 1 ~ cur -1 都为0 ,cur ~ n-1为待处理元素
2的n次方
2024/10/15
1490
双指针算法详解
相关推荐
​LeetCode刷题实战611:有效三角形的个数
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验