牛客网——牛牛的数组匹配

简介: 牛客网——牛牛的数组匹配

前言:


不知不觉连续更了21天,(为书包而奋斗),和大家一起学习了21天,虽然有时候太忙就水文章,但是还是学到了很多,认识了很多小伙伴,真的很开心~

今天咱一起学习一下牛牛的数组匹配哈。

一、牛牛的数组匹配


题目:

牛牛的数组匹配_牛客题霸_牛客网

描述


牛牛刚学会数组不久,他拿到两个数组 a 和 b,询问 b 的哪一段连续子数组之和与数组 a 之和最接近。

如果有多个子数组之和同样接近,输出起始点最靠左的数组。

输入描述:


第一行输入两个正整数 n 和 m ,表示数组 a 和 b 的长度。

第二第三行输入 n 个和 m 个正整数,表示数组中 a 和 b 的值。

输出描述:


输出子数组之和最接近 a 的子数组

二、解题过程


#include<stdio.h>
/*思路:从完整数组开始,不断去掉前面的一个元素,用剩下的子数组进行下轮比较;
*每轮判断规则(如果满足减去数组2当前的最后一个元素后,如果和数组1差值变小了,
*就继续减去尾元素,直到满足差值最小,得到本轮最优解; 用该值和下一轮进行比较,
*如果下一轮差值更小,则继续切割数组,找更下一轮,直到不满足,然后根据i,j位置输出数组元素;
*/
#include <stdio.h>
int num(int a,int b)
{
  if(a>=b)
  return a-b;
  else
  return b-a;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int a[100]={0};
    int b[100]={0};
    int sum1=0,sum2=0,min,k,l;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
  for(int i=0;i<n;i++)
  {
    sum1+=a[i];
  }
  min=sum1;
  for(int i=0;i<m;i++)
  {
    sum2=b[i];
    for(int j=i+1;j<=m;j++)
    {
      if(num(sum1,sum2)<min)
      {
        min=num(sum1,sum2);
        k=i;
        l=j;
      }
      sum2+=b[j];
    }
  }
  for(int i=k;i<l;i++)
  {
    printf("%d ",b[i]);
  }
    return 0;
}

总结


以上就是今天要讲的内容,本文只是简单介绍了一种解题方法,希望对大家有帮助~

相关文章
|
8月前
|
Java
每日一题《剑指offer》数组篇之数组中重复的数字
每日一题《剑指offer》数组篇之数组中重复的数字
59 0
每日一题《剑指offer》数组篇之数组中重复的数字
|
8月前
|
Java 测试技术 Python
每日一题《剑指offer》字符串篇之表示数值的字符串
每日一题《剑指offer》字符串篇之表示数值的字符串
56 0
每日一题《剑指offer》字符串篇之表示数值的字符串
|
8月前
|
Java
每日一题《剑指offer》数组篇之数组中只出现一次的两个数字
每日一题《剑指offer》数组篇之数组中只出现一次的两个数字
39 0
每日一题《剑指offer》数组篇之数组中只出现一次的两个数字
|
8月前
|
Java
每日一题《剑指offer》字符串篇之字符串的排列
每日一题《剑指offer》字符串篇之字符串的排列
82 0
每日一题《剑指offer》字符串篇之字符串的排列
|
8月前
|
算法
六六力扣刷题字符串之重复的子字符串
六六力扣刷题字符串之重复的子字符串
71 0
|
存储 算法 C++
【数据结构与算法】哈希表1:字母异位词 & 两数交集 & 快乐数 & 两数之和
【数据结构与算法】哈希表1:字母异位词 & 两数交集 & 快乐数 & 两数之和
88 0
【牛客】字符集合
【牛客】字符集合
93 0
【牛客】字符集合
|
机器学习/深度学习 NoSQL Shell
力扣刷题记录——344.反转字符串、345.反转字符串中的元音、349.两个数组的交集
力扣刷题记录——344.反转字符串、345.反转字符串中的元音、349.两个数组的交集
105 0
力扣刷题记录——344.反转字符串、345.反转字符串中的元音、349.两个数组的交集
力扣刷题记录——521. 最长特殊序列 Ⅰ、541. 反转字符串 II、557. 反转字符串中的单词 III
力扣刷题记录——521. 最长特殊序列 Ⅰ、541. 反转字符串 II、557. 反转字符串中的单词 III
121 0
力扣刷题记录——521. 最长特殊序列 Ⅰ、541. 反转字符串 II、557. 反转字符串中的单词 III
力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数
力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数
159 0
力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数