寫在前面～

最近朋友面試遇到了這道題

發(fā)來和小媛一起討論的時候

突然覺得說這是一道雖然簡單，但是仍然可以討論一下的「medium」題目

決定發(fā)出來分享一下

這道題有比較容易想到的「O（n） 時間復雜度」的解法

但是難免有的面試官會＂精益求精＂

進階的詢問是否有「O（n log（n）） 時間復雜度」的解法

這就需要大家動動小腦瓜啦～（其實也不難想到）

閑話少說～

先來看題～

題目

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。

找出該數(shù)組中滿足 其和 ≥ target 的 長度最小的 連續(xù)子數(shù)組

［nums＿l， nums＿l＋1， ．．．， nums＿r－1， nums＿r］ ，

并返回其長度。

如果不存在符合條件的子數(shù)組，返回 0 。

示例 1：

輸入：target ＝ 7， nums ＝ ［2，3，1，2，4，3］

輸出：2

解釋：子數(shù)組 ［4，3］ 是該條件下的長度最小的子數(shù)組。

示例 2：

輸入：target ＝ 4， nums ＝ ［1，4，4］

輸出：1

示例 3：

輸入：target ＝ 11， nums ＝ ［1，1，1，1，1，1，1，1］

輸出：0

提示：

1 ＜＝ target ＜＝ 109

1 ＜＝ nums．length ＜＝ 105

1 ＜＝ nums［i］ ＜＝ 105

先停在這里

思考一會兒～

你會用什么方法呢

一、滑動窗口 ／ 雙指針

思路：

· 定義兩個指針 start 和 end 分別表示子數(shù)組（滑動窗口窗口）的開始位置和結束位置

· 維護變量 sum 存儲子數(shù)組中的元素和

· 初始狀態(tài)下，start 和 end 都指向下標 0，sum 的值為 0

· 每一輪迭代，將 nums［end］ 加到 sum，如果 sum≥s，則更新子數(shù)組的最小長度，然后將 nums［start］ 從 sum 中減去并將 start 右移，直到 sum＜s，在此過程中同樣更新子數(shù)組的最小長度

· 在每一輪迭代的最后，將 end 右移。

復雜度分析：

· 時間復雜度：O（n），其中 n 是數(shù)組的長度。指針 start 和 end 最多各移動 n 次。

· 空間復雜度：O（1）。c

二、前綴和 ＋ 二分查找

思路：

· 因為這道題保證了數(shù)組中每個元素都為正，所以前綴和一定是遞增的，這一點保證了二分的正確性。如果題目沒有說明數(shù)組中每個元素都為正，這里就不能使用二分來查找這個位置了。

· 在確定每個子數(shù)組的開始下標后，找到長度最小的子數(shù)組需要 O（n） 的時間。

· 如果使用二分查找，則可以將時間優(yōu)化到 O（logn）。

復雜度分析：

· 時間復雜度：O（nlogn），其中 n是數(shù)組的長度。需要遍歷每個下標作為子數(shù)組的開始下標，遍歷的時間復雜度是 O（n），對于每個開始下標，需要通過二分查找得到長度最小的子數(shù)組，二分查找得時間復雜度是 O（logn），因此總時間復雜度是 O（nlon）。

· 空間復雜度：O（n），其中 n 是數(shù)組的長度。額外創(chuàng)建數(shù)組 sums 存儲前綴和。

       原文標題 : 209 | 長度最小的子數(shù)組