当前位置:网站首页>611. 有效三角形的个数
611. 有效三角形的个数
2022-07-05 07:18:00 【BugMaker-shen】
此时 n u m s [ l ] + n u m s [ m i d ] > n u m s [ r ] nums[l] + nums[mid] > nums[r] nums[l]+nums[mid]>nums[r], l l l取 [ l , m i d − 1 ] [l,mid-1] [l,mid−1]内任何一个数都满足条件,故有 a n s + = ( m i d − l ) ans += (mid - l) ans+=(mid−l)
我们现在的三元组(2,6,7)满足条件了,由于不等式右侧nums[r]固定,我们需要做的是调整不等式左侧的大小,尽可能让不等式满足
由于我们让 l l l取 [ l , m i d − 1 ] [l,mid-1] [l,mid−1]内任何一个数就是尝试了让不等式左侧变得更大(依然满足条件),我们现在应该让不等式左侧变得更小,继续查看是否满足三角形条件,即向左移动mid,继续查找三元组
不满足条件时,两个小数字的和太小了,要让不等式左侧变大,只有一个选择:向右移动 l l l取更大的数
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), less<int>());
int n = nums.size();
int ans = 0;
// 每轮循环固定最大的数字不动
for (int r = n - 1; r >= 2; r--){
int l = 0;
int mid = r - 1;
while(l < mid){
if(nums[l] + nums[mid] > nums[r]){
ans += (mid - l);
// mid是从r-1开始的,mid初始值较大,现在已经满足三角形条件,需要在较小数字中找满足三角形条件的数字
mid--;
}else{
// 两个小数字的和太小了
l++;
}
}
}
return ans;
}
};
那我们可以固定最小的值,用mid和r寻找三元组吗?
这种情况下,不满足三角形条件,两个小数字之和太小了,我们可以向右调整 m i d mid mid让 n u m s [ l ] + n u m s [ m i d ] nums[l]+nums[mid] nums[l]+nums[mid]的值更大,或向左调整 r r r,让 n u m s [ r ] nums[r] nums[r]的值更小,以满足三角形不等式。这操作起来就比较困难了:
我们向右调整mid,mid指向3,我们会漏掉(2,2,3)这个组合;向左调整r,r指向3,我们会漏掉(2,3,4)这个组合
所以我们应该把用于搜索三元组的两个指针放在不等式的同一侧,使得不满足三角形不等式时只有一个选择
边栏推荐
- 并发编程 — 死锁排查及处理
- 纯碱是做什么的?
- Powermanagerservice (I) - initialization
- Altimeter data knowledge point 2
- DataGrid offline installation of database driver
- M2dgr slam data set of multi-source and multi scene ground robot
- Ros2 - install ros2 (III)
- 2022.06.27_每日一题
- Course learning accumulation ppt
- [node] differences among NPM, yarn and pnpm
猜你喜欢
[software testing] 02 -- software defect management
目标检测系列——Faster R-CNN原理详解
2022年PMP项目管理考试敏捷知识点(7)
Powermanagerservice (I) - initialization
Tshydro tool
Ros2 - common command line (IV)
Machine learning Seaborn visualization
Three body goal management notes
Concurrent programming - deadlock troubleshooting and handling
[node] NVM version management tool
随机推荐
网易To B,柔外刚中
Unity ugui how to match and transform coordinates between different UI panels or uis
[software testing] 03 -- overview of software testing
NPM and package common commands
SD_CMD_RECEIVE_SHIFT_REGISTER
C#学习笔记
DelayQueue延迟队列的使用和场景
Ggplot2 drawing learning notes in R
【软件测试】05 -- 软件测试的原则
[tf1] save and load parameters
Ros2 - common command line (IV)
Import CV2, prompt importerror: libcblas so. 3: cannot open shared object file: No such file or directory
An article was opened to test the real situation of outsourcing companies
Qu'est - ce que l'hydroxyde de sodium?
GPIO port bit based on Cortex-M3 and M4 with operation macro definition (can be used for bus input and output, STM32, aducm4050, etc.)
Raspberry pie 4B arm platform aarch64 PIP installation pytorch
能量守恒和打造能量缺口
Executealways of unity is replacing executeineditmode
Course learning accumulation ppt
The difference between new and malloc