算法筆試模拟題精解之“相似數組”

線上程式設計産品介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。

點選連結開始體驗：

https://developer.aliyun.com/coding

題目描述

等級：中等

知識點：貪心、尺取法

檢視題目：77.相似數組

現在有兩個數組 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])

重複以上過程，即可求解。

是不是有思路了呢，點選連結立刻答題：

77.相似數組 另有線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！