【C语言刷题系列】求一个数组中两个元素a和b的和最接近整数m

用户11396077

发布于 2024-12-06 18:56:47

12200

代码可运行

文章被收录于专栏：C/C++指南C/C++指南

运行总次数：0

代码可运行

一、问题描述

给定一个整数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;
}