【算法专题突破】双指针 - 有效三角形的个数(5)

简介: 【算法专题突破】双指针 - 有效三角形的个数(5)

1. 题目解析

题目链接:611. 有效三角形的个数 - 力扣(Leetcode)

我们可以根据示例1来理解这一道题目,

他说数组里面的数可以组成三角形三条边的个数,

那我们先自己枚举一下所有情况看看:

【2, 2, 3】

【2, 2, 4】

【2, 3, 4】

【2, 3, 4】

总共是四种情况,

而第二种情况是不成立的,看看示例,我们可以知道,虽然都是2,

但是不同位置可以看成不同的元素。

2. 算法原理

一开始我们看到这样的题目,实际上第一个想到的解法就是暴力枚举,

把所有情况枚举一遍然后判断,但是这是一个O(N3)的解法,

我们可以通过单调性和双指针的方式来优化我们的时间复杂度,

具体思路如下:

1. 通过sort 找到最大值

2. 使用双指针快速求出符合题目要求的数

具体操作如下:

以这个排好序的数组为例:

左指针指向最小的元素,右指针指向最大元素的左边元素,

跟据三角形两边之和需要大于第三边的性质,

如果 2 + 9 > 10,就证明 3 + 9,4 + 9 等等情况都会大于10,

这样我们就直接计算出 right - left 种适合的情况,

这样就能让所有的数都跟 9 结合过了,就让 right--。

 

如果 2 + 5 <= 10,就证明无论是 2 + 4 还是 2 + 3 等等情况,都会<=10,

所以我们就能直接让 left++,去找更大的数。

最后等left 和 right 相撞,就能求出所有适合的情况了。

3. 代码编写

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        for(int i = nums.size() - 1; i > 1; i--) {
            int left = 0, right = i - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    ans += (right - left);
                    right--;
                }
                else left++;
            }
        }
        return ans;
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

相关文章
|
2月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
63 4
双指针算法详解
|
1月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
3月前
|
数据采集 算法
基于PSO粒子群算法的三角形采集堆轨道优化matlab仿真
该程序利用PSO算法优化5个4*20矩阵中的模块采集轨迹,确保采集的物品数量及元素含量符合要求。在MATLAB2022a上运行,通过迭代寻优,选择最佳模块组合并优化轨道,使采集效率、路径长度及时间等综合指标最优。具体算法实现了粒子状态更新、需求量差值评估及轨迹优化等功能,最终输出最优轨迹及其相关性能指标。
|
3月前
|
算法 容器
【算法】双指针
【算法】双指针
|
3月前
|
算法 数据建模
平面中判断点在三角形内算法(重心法)
平面中判断点在三角形内算法(重心法)
45 0
|
3月前
|
算法 C++
空间中判断点在三角形内算法(方程法)
空间中判断点在三角形内算法(方程法)
59 0
|
3月前
|
算法
平面中判断点在三角形内算法(同向法)
平面中判断点在三角形内算法(同向法)
26 0
|
3月前
|
算法 C++ Windows
空间射线与三角形相交算法的两种实现
空间射线与三角形相交算法的两种实现
42 0
|
3月前
|
算法 C++ 容器
【C++算法】双指针
【C++算法】双指针
下一篇
无影云桌面