💓 博客主頁：倔強的石頭的CSDN主頁
📝Gitee主頁：倔強的石頭的gitee主頁
? 文章專欄：C語言刷題系列
目錄
一、問題描述
二、解題思路
?解題思路：
解題步驟:
三、C語言代碼實現及測試
一、問題描述
給定一個整數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;
}
