思路大体就是滑动窗口的思想
思路:定义一个变量left和right用来指向brr数组的左边和右边,初始left=0;right=1;然后进入循环(条件就是left要一直再right的左边(left<right)并且right不能越界(right<m)
1.进入循环之后将left和right之间的数字加起来,判断与arr数组之和的差值是否小于min,小于则更新min的值然后将left和right的值保存方便后面输出。
2.然后判断sum的值是大于numa(数组arr之和)则left++;小于则right++;不断调整滑动窗口最后递归完数组全部元素,保存在min的里面就是最小差,cl,cr里面就是min的对应的数组区间。
注意:要先判断sum和min的关系然后再调整滑动窗口,不然会造成本来这个sum已经是最接近的了,但是因为不等于numa导致滑动窗口移动了,对应的sum也就不对了。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
/*int cmp(const void*str1,const void*str2)
{
return *(int *)str1 - *(int*)str2;
}
*/
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int arr[n];
int brr[m];
int numa=0;
int i =0;
int j = 0;
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
numa+=arr[i];
}
for(j=0;j<m;j++)
{
scanf("%d",&brr[j]);
}
//qsort(brr,m,sizeof(int),cmp);
int left = 0;
int right = 1;
int min = numa;
int sum = 0;
int cl = 0;
int cr = 0;
if(m==1)
{
printf("%d",brr[0]);
return 0;
}
while(left < right && right<m)
{
sum = 0;
// sum = brr[left]+brr[right];
for(int i=left;i<=right;i++)
{
sum+=brr[i];
}
if(abs(sum-numa) < min)
{
min = abs(sum-numa);
cl=left;
cr=right;
}
if(sum>numa)
{
left++;
}
if(sum<numa)
{
right++;
}
}
for(int i = cl;i<=cr;i++)
{
printf("%d ",brr[i]);
}
return 0;
}