一、问题描述
给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum
注意：
给定的数组是有序的
a和b是全局变量，不需要返回值
二、解题思路
解题思路：
利用数组的有序性，通过双指针在数组中同时从两端向中间遍历，逐步逼近目标和，从而找到最接近给定和的两个数
解题步骤:
初始化变量
- 创建两个变量left和right分别指向数组首尾（相当于左指针和右指针）
- 创建一个整型变量min_diff存储两个元素的差值，初始化为整型最大值
双指针遍历
- while循环，循环条件是左右指针未相遇
- 循环中对left和right指向的元素相加求和存放到变量sum中
- 先判断，将sum与整数m进行比较，如果相等的话，直接将两个元素赋值给a和b，return即可
- 如果不相等再执行下面代码
- 求sum与整数m做差的绝对值，将差值绝对值与min_diff进行比较
- 如果新的差值较小，则min_diff等于新的差值，并改变a和b为当前的left和right指向的两个元素
- 接下来将sum与整数m进行比较
- 如果sum较大，right--
- 如果sum较小，left++
输出结果
- 出循环时，a和b存储的就是最接近整数m的值
三、C语言代码实现及测试
//求一个数组中两个元素a和b的和最接近整数m #include<stdio.h> #include<limits.h> int a = 0, b = 0;//全局变量 void fun(int* arr, int numsSize,int m) { int left = 0;//左指针 int right = numsSize - 1;//右指针 int min_diff = INT_MAX;//存储最小差值 while (left <= right) { int sum = arr[left] + arr[right]; if (sum == m)//如果元素和等于m，直接返回 { a = arr[left]; b = arr[right]; return; } int tmp_diff = abs(sum - m);//存储当前差值 if (tmp_diff < min_diff)//如果当前元素更接近，更新数据 { min_diff = tmp_diff; a = arr[left]; b = arr[right]; } if (sum > m) right--; if (sum < m) left++; } } int main() { int arr[] = { 2,4,6,8,10,11,14,16,18 }; int sz = sizeof(arr) / sizeof(arr[0]); int m = 13; fun(arr, sz, m); printf("最接近整数m=%d的a和b的值是%d,%d\n", m, a, b); return 0; }
