力扣算法题——611.有效三角形的个数
目录
💕1.题目
💕2.解析思路
本题思路总览
借助排序与双指针探索规律
从规律到代码实现的转化
双指针的具体实现
代码整体流程
💕3.代码实现
💕4.完结
二十七步也能走完逆流河吗
💕1.题目
💕2.解析思路
本题思路总览
力扣题目要求从给定的整数数组
nums
中找出可以构成三角形的三元组数量。根据三角形的性质,对于三条边a
、b
、c
,需要满足任意两边之和大于第三边,即a + b > c
、a + c > b
且b + c > a
。当数组有序时,只要满足最小的两边之和大于最大边,就可以构成三角形。我们采用排序加双指针的方法,先对数组进行排序,然后固定最大边,使用双指针在其左侧寻找满足条件的另外两条边,通过统计符合条件的组合数量得到最终结果。
借助排序与双指针探索规律
- 排序的作用
对数组
nums
进行排序后,数组元素从小到大排列。这样在后续寻找三角形组合时,我们可以固定最大边,只需要关注较小的两条边之和是否大于最大边这一个条件,简化了判断逻辑。
- 双指针的运用
使用三个指针
a
、b
、c
,其中c
指向当前考虑的最大边,b
和a
作为双指针在c
左侧的元素中移动。b
初始化为c - 1
,a
初始化为数组起始位置。通过移动a
和b
指针,在a < b
的条件下,不断检查nums[a] + nums[b]
与nums[c]
的大小关系,从而找出所有满足条件的组合。
从规律到代码实现的转化
基于上述排序和双指针的规律,我们在代码中首先对数组进行排序,然后通过两层循环来实现指针的移动和条件判断。外层循环固定最大边
c
,从数组末尾向前移动;内层循环使用双指针a
和b
在c
左侧寻找满足三角形条件的组合,并统计组合数量。
双指针的具体实现
- 指针定义
a
:作为左指针,初始时指向数组的第一个元素,用于表示三角形的最小边。
b
:作为右指针,初始时指向c - 1
,用于表示三角形的中间边。
c
:用于固定当前考虑的最大边,初始时指向数组的最后一个元素。
2. 指针移动规则
当
nums[a] + nums[b] > nums[c]
时,说明以nums[b]
为中间边,nums[a]
到nums[b - 1]
都可以与nums[b]
和nums[c]
构成三角形,所以满足条件的组合数量增加b - a
个,然后将b
指针左移一位,继续寻找其他组合。当
nums[a] + nums[b] <= nums[c]
时,说明当前nums[a]
太小,需要将a
指针右移一位,尝试增大两边之和。
3. 终止条件
内层循环的终止条件是
a >= b
,表示已经遍历完当前c
固定时所有可能的a
和b
组合。外层循环的终止条件是c < 2
,因为当c
小于 2 时,无法构成三角形。
代码整体流程
- 数组排序
使用
sort(nums.begin(), nums.end())
对数组进行排序,确保数组元素按从小到大排列。
- 初始化变量
初始化计数器
count
为 0,用于统计满足条件的三角形组合数量。同时初始化指针a
、b
、c
,c
指向数组末尾,b
指向c - 1
,a
指向数组起始位置。
- 外层循环
从数组末尾开始,将
c
指针逐步向左移动,每次移动后更新b
指针为c - 1
,a
指针为数组起始位置。
- 内层循环
在
a < b
的条件下,根据nums[a] + nums[b]
与nums[c]
的大小关系移动a
和b
指针,并更新count
的值。
- 返回结果
当外层循环结束后,返回计数器
count
的值,即为可以构成三角形的三元组数量。通过以上步骤,我们可以利用排序和双指针准确找出数组中可以构成三角形的三元组数量。
💕3.代码实现
class Solution { public: int triangleNumber(vector<int>& nums) { //先排成有序 sort(nums.begin(),nums.end()); int a = 0; int c = nums.size()-1; int b = c-1; int count = 0; while(c>=2) { while(a<b){ if(nums[a]+nums[b]>nums[c]) { count += b-a; b--; //a = 0;可以没有 //因为b缩小了,如果想要大于c的话,a必须增大,没必要从头开始再遍历 } else { a++; } } c--; b = c-1; a = 0; } return count; } };