当前位置：网站首页>[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.
边栏推荐
- 牛客網：三數之和
- Demand and business model analysis-3-design
- What is a hash index?
- Connectez - vous à MySQL
- PostgreSQL database replication - background first-class citizen process walreceiver PG_ stat_ wal_ Receiver view
- 2 R programming
- 【GAMES101】课堂笔记8–着色（着色频率、图形管线、纹理映射）
- What does MySQL full value match mean
- 94. analyze the content in the web page
- MySQL log
猜你喜欢
Parameter meaning of random forest randomforestclassifier in sklearn
Process creation fork (), demise wait()
sklearn中随机森林RandomForestClassifier的参数含义
Macro definitions and functions
Understand Jack Dorsey's web5 from the ppt on page 16
Demand and business model analysis-2-business model types
System log
exec函数、shell的实现
system（）
Reading small programs based on wechat e-book graduation design works (7) Interim inspection report
随机推荐
EFCore调优
The latest Ningxia construction safety officer simulation question bank and answers in 2022
[leetcode 7 solution] integer inversion
Handwritten promise
Demand and business model innovation - demand 3- demand engineering process
Demand and business model analysis-1-business model canvas
Bsn-ddc basic network introduction, technical features, unique advantages, application scenarios and platform access
I learned database at station B (10): View
2022年，中国大学生最多的20个城市
Generate API documents using swagger (go language example)
const
Wall Street cheat sheet
Golden, silver and four job hopping season, teach you these tips to improve the interview success rate
Torch network model is converted to onnx format and visualized
1. Getting to know R
Operating instructions for installing mysql5.7 in centos7
The joint empowerment plan of Baidu PaddlePaddle large enterprise open innovation center was launched! Help Pudong to upgrade its industry intelligently
Demand and business model innovation-5-process
How mysterious is "PIP not an internal or external command, nor a runnable program or batch file"
Test prerequisites: recommend a special cross platform app performance test tool!