当前位置：网站首页>[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.
边栏推荐
- Wall Street cheat sheet
- BigTable (II): how BigTable achieves scalability and high performance
- 【生成对抗网络学习 其三】BiGAN论文阅读笔记及其原理理解
- Interpreter Files
- MySQL - the execution order of an SQL statement
- PostgreSQL数据库复制——后台一等公民进程WalReceiver pg_stat_wal_receiver视图
- Demand and business model innovation - demand 4- overview of demand acquisition
- const
- Scalars, vectors, arrays, and matrices
- Microsoft Word tutorial, how to insert a header or footer in word?
猜你喜欢
解释器文件
Wechat e-book reading applet graduation design work (6) opening defense ppt
一致性哈希的简单认识
Interpreter Files
Implementation of exec function and shell
Demand and business model innovation-5-process
Niuke.com: sum of three numbers
When will the index fail
Compilation of programs
Axure RP 9 for Mac(交互式产品原型设计工具)中文版
随机推荐
Wechat applet notes
2022年，中国大学生最多的20个城市
Unsupported class file major version 60
Installation and testing of open source deep learning framework plaidml
MySQL index classification
What does MySQL full value match mean
牛客网：三数之和
Macro definitions and functions
The joint empowerment plan of Baidu PaddlePaddle large enterprise open innovation center was launched! Help Pudong to upgrade its industry intelligently
Efcore tuning
QT pro文件配置ffmpeg宏
系统 日志
Theory + practice will help you master the dynamic programming method
Low code enables rural construction to open "smart mode"
What is disk IO?
Index optimization principle
BigTable (II): how BigTable achieves scalability and high performance
Solve NPM compilation times node_ modules/optipng-bin/vendor/optipng ENOENT
Go memory escape analysis
When will the index fail