算法筆試模拟題精解之“超級區間”

線上程式設計介紹

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

https://developer.aliyun.com/coding

本文為大家介紹其中的第57題：超級區間 的題目解析，具體如下：

題目描述

題目等級：中等

知識點：二分查找、尺取法

檢視題目：超級區間

Tom現在有一個長度為n的數組，Jerry給Tom定義了一種超級區間，如果區間[l,r]滿足(a[l]+…+a[r])>=k,則區間[l,r]被稱為超級區間，現在Jerry想讓Tom告訴他數組中有多少個超級區間。

輸入整數n,整數k(1<=n,k<=100000)，和一個大小為n的數組，數組的每個元素的大小都在[1,1000]之間。

輸出輸入數組的超級區間的個數。

示例1

輸入：

3

5

[2,3,5]

輸出：

4

注意

樣例滿足條件的超級區間為

[1,2],[2,3],[1,3],[3,3]。

解題思路：尺取法

使用 尺取法 對搜尋空間進行周遊。

設目前區間為[L, R]。初始L = R = 0；使用尺取法需要判斷什麼時候調整L和R。

數組中的所有數都為正數。

情況1：假設對于某個區間[L1, R1]滿足超級區間的定義。因為所有數都為正數，是以保持L1不變，依次增加R1直到n為止的所有區間都滿足超級區間的定義。

情況2：假設對于某個區間[L2，R2]不滿足超級區間的定義。則需要保持L2不動，增加R2才可能滿足超級區間的定義。

情況3：是情況2拓展。如果[L2，n]不滿足超級區間的定義，則任何i>L2，區間[i, n]都不滿足超級區間的定義。

計算過程

1. 初始L = R = 0；sum = 0; 用來計算滿足條件的區間個數

2. 判斷區間 [L, R] 的情況，滿足情況1，則sum++; R++。滿足情況2， L++。滿足情況3，結束計算。

   對于情況1，因為L不變時，後面的所有R都滿足條件，是以可以修改為sum+=n-R+1； L++。

時間複雜度O(n^2) 修改之前最差為O(n^2)

空間複雜度O(1) 記錄目前區間數組元素的和

看完之後是不是有了想法了呢，快來練練手吧>>