当前位置:网站首页>[leetcode16] the sum of the nearest three numbers (double pointer)
[leetcode16] the sum of the nearest three numbers (double pointer)
2022-07-06 05:02:00 【Evening scenery at the top of the mountain】
One 、 subject
Two 、 Ideas
and leetcode15 The sum of three is similar , Three level cycle time complexity O ( n 3 ) O(n^3) O(n3) Too high , Use double pointer, although it can't drop to O ( n ) O(n) O(n), But it is the common routine of this kind of questions :
- Go through the array elements , The current element is
num[i]
; - Set the left and right pointers , The right pointer is the right endpoint , Note that the left pointer is
left + 1
, Not from 0 Start , Otherwise, there will be repeated elements due to repeated traversal ; When the sum of three numbers is greater thantarget
beright
Move left to reduce the value . - Every time we judge the current combination of three numbers , That is, calculate and target Difference between , If it is lower than the current minimum difference
minAbsError
Still small , You can update .
3、 ... and 、 Code
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0, left = 0, right = 0;
int minAbsError = INT_MAX, error = 0, absError = 0, temp = 0;
for(int i = 0; i < nums.size() - 2; i++){
left = i + 1;
right = nums.size() - 1;
while(left < right){
temp = nums[i] + nums[left] + nums[right];
error = temp - target;
absError = abs(error);
if(minAbsError > absError){
// The update process
ans = temp;
minAbsError = absError;
}else if(error > 0){
right--;
}else{
left++;
}
}
}
return ans;
}
};
边栏推荐
- Postman管理测试用例
- Application of Flody
- Request (request object) and response (response object)
- RTP gb28181 document testing tool
- JS quick start (II)
- 你需要知道的 TCP 三次握手
- 關於Unity Inspector上的一些常用技巧,一般用於編輯器擴展或者其他
- 麦斯克电子IPO被终止:曾拟募资8亿 河南资产是股东
- The IPO of mesk Electronics was terminated: Henan assets, which was once intended to raise 800 million yuan, was a shareholder
- Luogu deep foundation part 1 Introduction to language Chapter 2 sequential structure programming
猜你喜欢
Class inheritance in yyds dry inventory C
DMA use of stm32
[lgr-109] Luogu may race II & windy round 6
ISP learning (2)
[数学建模] 微分方程--捕鱼业的持续发展
麦斯克电子IPO被终止:曾拟募资8亿 河南资产是股东
Embedded development program framework
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Postman管理测试用例
Postman manage test cases
随机推荐
Summary of redis AOF and RDB knowledge points
Application of Flody
Postman测试报告
Luogu deep foundation part 1 Introduction to language Chapter 2 sequential structure programming
Postman关联
Cve-2019-11043 (PHP Remote Code Execution Vulnerability)
关于imx8mp的es8316的芯片调试
8. Static file
Leetcode 186 Flip the word II in the string (2022.07.05)
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Request (request object) and response (response object)
Introduction of several RS485 isolated communication schemes
团队协作出了问题,项目经理怎么办?
Compilation et connexion de shader dans games202 - webgl (comprendre la direction)
[数学建模] 微分方程--捕鱼业的持续发展
Postman前置脚本-全局变量和环境变量
Project manager, can you draw prototypes? Does the project manager need to do product design?
Driver development - hellowdm driver
Fuzzy -- basic application method of AFL
2021 RoboCom 世界机器人开发者大赛-本科组(复赛)