算法笔试模拟题精解之“相似数组”

算法笔试模拟题精解之“相似数组”

贡献者 | 张鹏飞

简介：要解出相似数组的最长长度，即要求相似数组中的每个元素尽可能的小，

把握这一点，结合下来的算法过程理解一下。

题目描述

等级：中等

知识点：贪心、尺取法

查看题目：相似数组

现在有两个数组 a 和 b，长度分别为 n 和 m。你可以对两者进行任意次数（包

括零次）的下述操作：

任选一段连续的区间 [l, r]，将其替换为这段区间的所有数字的和。比如，对于

[1, 3, 4, 5, 11, 9]，你可以选择区间 [3, 5]，并将其替换为 4+5+11=20，操作后的数

组为 [1, 3, 20, 9]。

你现在需要通过上述操作将两个数组变成相同的数组，相同的定义是：对于两个

数组 a，b 必须长度相同，不妨设为 l，并且对于 1 <= i <= l，必有 a[i]=b[i]。

如果这两个数组可以变成相同的数组，那么我们称这两个数组是相似数组，否则

不是相似数组。我们并不在意操作的次数，我们只在意在这两个数组经过操作之后变

成相同数组的时候最长的长度是多少，如果它们本来不相似请输出 -1。

输入内容为四个部分，先两个数字 n、m（1 <= n, m <= 100000），分别表示数

组 a 和 b 的长度，再分别输入含有 n 个数字的数组 a 和含有 m 个数字的数组 b，其

中 1 <= a[i], b[i] <= 1000000000。

输出一个数字，表示最长的长度。

示例 1

输入：

5

4

[7,2,5, 11, 13]

[9 ,16 ,6 ,7 ]

输出：

3

解题思路

要解出相似数组的最长长度，即要求相似数组中的每个元素尽可能的小，把握这

一点，结合下文的算法过程理解一下。

设两个指针，分别指向数组 a 和 b 的第一个位置（即 i=0，j=0)，定义两个变量，

分别表示数组 a 和 b 的当前区别的和（sum_a=a[0], sum_b=b[0])，然后遍历数组。

如果 sum_a==sum_b：

则结果加 1( 即 ans++)，然后对两个指针分别加 1(i++, j++)。

判断：如果两个指针都等于各自数组的长度 ( 即 i==n&&j==m)，则返回结果

(return ans）；

如果两个指针仅有一个等于数组的长度（即 i=n || j=m)，则返回 -1（表示不是相

似数组 )；

如果以上两个条件都不满足 ( 即两个指针都小于数组长度 )，则当前区间和更新

为此时指向的元素 ( 即 sum_a=a[i], sum_b=b[j])。

如果 sum_a 则数组 a 的指针向前移动（即 i++），判断 i 是否越界 ( 即 i==n 为真

表示越界 )，如果越界，那么返回 -1( 表示不是相似数组 )，

如果没越界，给区别和加上当前元素 ( 即 sum_a+a[i])

如果 sum_a>sum_b:

则数组 b 的指针向前移动（即 j++），判断 j 是否越界 ( 即 j==m 为真表示越界 )，

如果越界，那么返回 -1( 表示不是相似数组 )，

如果没越界，给区别和加上当前元素 ( 即 sum_b+a[b])

重复以上过程，即可求解。

是不是有思路了呢，点击链接立刻答题：相似数组