当前位置：网站首页>[leetcode 16 solution] the sum of the nearest three numbers
[leetcode 16 solution] the sum of the nearest three numbers
2022-06-12 20:14:00 【along】
One 、 subject
Given an include n Array of integers nums and A target value target. find nums Three integers in , Make their sum and target Nearest . Returns the sum of the three numbers . Assume that there is only one answer for each group of input .
Example ：
Input ：nums = [-1,2,1,-4], target = 1
Output ：2
explain ： And target The closest and 2 (-1 + 2 + 1 = 2) .
- 1.
- 2.
- 3.
Tips ：
-
3 <= nums.length <= 10^3 -
-10^3 <= nums[i] <= 10^3 -
-10^4 <= target <= 10^4
Two 、 Answer key ： Two way sorting + Three pointer bubbling method
The direction of the three pointers is ：
The following two optimizations are added to the code :
- The last pointer data is de duplicated
- Because the array has been sorted , If appear The absolute value The increase of , It is said that the following numbers are no smaller , This round can break Jump out of .
// Sort the array
void sort_array(int *nums, int numsSize){
int i;
int *current, *left, *right, *tmp;
printf(" Before ordering ：");
for(i = 0; i<numsSize; i++)
printf(" %-3d ", nums[i]);
printf("\n");
left = nums;
right = nums + numsSize - 1;
while(left < right){
current = left;
while( current < right){
if(*left > *current || *current > *right)
{
tmp = *left > *current ? left : right;
i = *current;
*current = *tmp;
*tmp = i;
}
current++;
}
left++;
right--;
}
printf(" After ordering ：");
for(i = 0; i<numsSize; i++)
printf(" %-3d ", nums[i]);
printf("\n");
}
// Solve the absolute value
int get_abs(int a, int b, int c, int target){
return target > (a+b+c) ? target-(a+b+c) : (a+b+c)-target;
}
int threeSumClosest(int* nums, int numsSize, int target){
int *current, *left, *right;
int abs_nums=65535, pre_abs, result=0;
// Sort the array
sort_array(nums, numsSize);
current = nums;
while(current < nums + numsSize - 2){
left = current + 1;
while(left < nums + numsSize - 1 ){
right = left + 1;
pre_abs=65535; // Use pre_abs Used to determine whether subsequent calculations need to be continued
while(right <= nums + numsSize - 1){
//printf("current=%-3d left=%-3d right=%-3d abs=%-3d result=%-3d\n", *current, *left, *right, get_abs(*current,*left,*right,target), result );
if( abs_nums >= get_abs(*current,*left,*right,target) )
{
abs_nums = get_abs(*current,*left,*right,target);
result = *current + *left + *right;
pre_abs = abs_nums;
}
else if(pre_abs < get_abs(*current,*left,*right,target))
{
printf(" It's getting bigger , The current wheel is the smallest abs_nums=%d , break\n", abs_nums );
break;
}
while( ++right <= nums + numsSize - 1 && *right == *(right-1)); // right It's worth it
//right++;
}
left++;
}
current++;
}
return result;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
- 79.
- 80.
The operation process is as follows ：
Input :
[1,2,4,8,16,32,64,128]
82
Output : 82
Before ordering ： 1 2 4 8 16 32 64 128
After ordering ： 1 2 4 8 16 32 64 128
current=1 left=2 right=4 abs=75 result=0
current=1 left=2 right=8 abs=71 result=7
current=1 left=2 right=16 abs=63 result=11
current=1 left=2 right=32 abs=47 result=19
current=1 left=2 right=64 abs=15 result=35
current=1 left=2 right=128 abs=49 result=67
It's getting bigger , The current wheel is the smallest abs_nums=15 , break
current=1 left=4 right=8 abs=69 result=67
current=1 left=4 right=16 abs=61 result=67
current=1 left=4 right=32 abs=45 result=67
current=1 left=4 right=64 abs=13 result=67
current=1 left=4 right=128 abs=51 result=69
It's getting bigger , The current wheel is the smallest abs_nums=13 , break
current=1 left=8 right=16 abs=57 result=69
current=1 left=8 right=32 abs=41 result=69
current=1 left=8 right=64 abs=9 result=69
current=1 left=8 right=128 abs=55 result=73
It's getting bigger , The current wheel is the smallest abs_nums=9 , break
current=1 left=16 right=32 abs=33 result=73
current=1 left=16 right=64 abs=1 result=73
current=1 left=16 right=128 abs=63 result=81
It's getting bigger , The current wheel is the smallest abs_nums=1 , break
current=1 left=32 right=64 abs=15 result=81
current=1 left=32 right=128 abs=79 result=81
current=1 left=64 right=128 abs=111 result=81
current=2 left=4 right=8 abs=68 result=81
current=2 left=4 right=16 abs=60 result=81
current=2 left=4 right=32 abs=44 result=81
current=2 left=4 right=64 abs=12 result=81
current=2 left=4 right=128 abs=52 result=81
current=2 left=8 right=16 abs=56 result=81
current=2 left=8 right=32 abs=40 result=81
current=2 left=8 right=64 abs=8 result=81
current=2 left=8 right=128 abs=56 result=81
current=2 left=16 right=32 abs=32 result=81
current=2 left=16 right=64 abs=0 result=81
current=2 left=16 right=128 abs=64 result=82
It's getting bigger , The current wheel is the smallest abs_nums=0 , break
current=2 left=32 right=64 abs=16 result=82
current=2 left=32 right=128 abs=80 result=82
current=2 left=64 right=128 abs=112 result=82
current=4 left=8 right=16 abs=54 result=82
current=4 left=8 right=32 abs=38 result=82
current=4 left=8 right=64 abs=6 result=82
current=4 left=8 right=128 abs=58 result=82
current=4 left=16 right=32 abs=30 result=82
current=4 left=16 right=64 abs=2 result=82
current=4 left=16 right=128 abs=66 result=82
current=4 left=32 right=64 abs=18 result=82
current=4 left=32 right=128 abs=82 result=82
current=4 left=64 right=128 abs=114 result=82
current=8 left=16 right=32 abs=26 result=82
current=8 left=16 right=64 abs=6 result=82
current=8 left=16 right=128 abs=70 result=82
current=8 left=32 right=64 abs=22 result=82
current=8 left=32 right=128 abs=86 result=82
current=8 left=64 right=128 abs=118 result=82
current=16 left=32 right=64 abs=30 result=82
current=16 left=32 right=128 abs=94 result=82
current=16 left=64 right=128 abs=126 result=82
current=32 left=64 right=128 abs=142 result=82
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
边栏推荐
- Axure RP 9 for Mac(交互式产品原型设计工具)中文版
- The execution results of i+=2 and i++ i++ under synchronized are different
- 2022年，中国大学生最多的20个城市
- Wechat e-book reading applet graduation design work (6) opening defense ppt
- Demand and business model innovation - demand 1 - Introduction to demand engineering
- Understand Jack Dorsey's web5 from the ppt on page 16
- [games101] class note 8 - shading (shading frequency, graphics pipeline, texture mapping)
- MySQL Basics
- 【生成对抗网络学习 其三】BiGAN论文阅读笔记及其原理理解
- Test prerequisites: recommend a special cross platform app performance test tool!
猜你喜欢
QT pro文件配置ffmpeg宏
Demand and business model analysis-3-design
Reading small program based on wechat e-book graduation design (4) opening report
Process creation fork (), demise wait()
Reading small programs based on wechat e-book graduation design works (7) Interim inspection report
Explain
How to determine fragment restored from Backstack
Deep feature synthesis and genetic feature generation, comparison of two automatic feature generation strategies
6 R factor and judgment Na
Installation and testing of open source deep learning framework plaidml
随机推荐
登录mysql
Demand and business model innovation-5-process
2022年最新宁夏建筑安全员模拟题库及答案
sklearn中随机森林RandomForestClassifier的参数含义
用户权限和组权限
Golden, silver and four job hopping season, teach you these tips to improve the interview success rate
Detailed explanation of SQL exists usage
进程会计、进程时间、守护进程
Axure RP 9 for Mac(交互式产品原型设计工具)中文版
Kyma application connectivity feature introduction
在 Traefik Proxy 2.5 中使用/开发私有插件(Traefik 官方博客)
PostgreSQL数据库复制——后台一等公民进程WalReceiver pg_stat_wal_receiver视图
Wechat e-book reading applet graduation design completion works (8) graduation design thesis template
The Milvus graphical management tool Attu is coming!
Demand and business model innovation - demand 2- demand basis
2 R programming
centos7 安装 mysql 5.7
Experience Technology Department of ant group launched the 2023rd school recruitment
Unsupported class file major version 60
Bsn-ddc basic network introduction, technical features, unique advantages, application scenarios and platform access