0862_和至少為 K 的最短子數組

題目描述

返回 A 的最短的非空連續子數組的長度，該子數組的和至少為 K 。

如果沒有和至少為 K 的非空子數組，返回 -1 。

示例1:

輸入：A = [1], K = 1 輸出：1 復制代碼

示例2:

輸入：A = [1,2], K = 4 輸出：-1 復制代碼

示例3:

輸入：A = [2,-1,2], K = 3 輸出：3 復制代碼

Note:

1. 1 <= A.length <= 50000 2. -10 ^ 5 <= A[i] <= 10 ^ 5 3. 1 <= K <= 10 ^ 9 復制代碼

暴力算法

func shortestSubarray(A []int, K int) int {minLen := 50001tail := len(A) - 1for i := 0; i <= tail; i++ {sum := A[i]if sum >= K {minLen = 1break}for j := i + 1; j <= tail; j++ {sum += A[j]if sum >= K {l := j - i + 1if l < minLen {minLen = l}break}}}if minLen != 50001 {return minLen}return -1 }復制代碼

高性能版本算法

func shortestSubarray(A []int, K int) int {size := len(A)sums := make([]int, size+1)for i, n := range A {if n >= K {return 1}sums[i+1] = sums[i] + n}res := size + 1//存儲0----i,有可能是符合條件的最短子串的headdeque := make([]int, 0, 0)for i := 0; i < size+1; i++ {for len(deque) > 0 && (sums[i]-sums[deque[0]] >= K) {// i 遞增// 可能有 j>i 使得 sums[j] - sums[deque[0]] >= K// 但是由于 j>i,所以deque[0]---i是以deque[0]作為頭的最短的符合條件的子串// 把 deque[0] 刪除res = min(res, i-deque[0])deque = deque[1:]}for len(deque) > 0 && (sums[i] <= sums[deque[len(deque)-1]]) {// 如果存在 j>i>deque[r] 使得 sums[j] - sums[deque[r]] >= K// 由于 sums[deque[r]] >= sums[i] 則// sums[j] - sums[i] >= K 一定成立，并且 j-i < j-deque[r]// 所以，以deque[r]作為頭,不可能是最短的符合條件子串,刪除deque = deque[:len(deque)-1]}deque = append(deque, i)}if res == size+1 {return -1}return res } 復制代碼

個人思路

相對于暴力破解,重復計算兩個元素之間的和,所以此處必須進行優化,只需要循環一遍數組,存儲0-i元素的和

假如a<b,sums[b]-sums[a]>=K,b-a則是子串長度

deque(雙端隊列)存儲0-i,可能符合條件的最短子串的head

遍歷sums,取deque的[0],判斷該元素作為子串的head,是否符合條件,如果符合條件,那么它將是該數組元素作為head的符合條件的子串中,最短的子串,從deque中剔除[0],減少后面的sums比次數

取deque的尾,值為r,sums[r]>=sums[i],那么如果后面存在sums[j]-sums[r]>=k,那么j>i>r,i->j之間的子串肯定也符合條件,并且更短,已r為head的子串,不可能是最短的字段,在這里可以刪除deque的這個尾,減少比對次數

總結

• 在leetcode社區中,有Java版本的算法代碼,思路和此處思路完全一致,但是時間效率比Golang版的搞,Golang版170ms左右,Java版本40+ms
• 筆者經過對比代碼,主要區別在于deque這個存儲容器,在JDK中有對應的數據結構Deque雙端隊列,數據結構的插入效率導致的,筆者猜測Java中該結構用的雙向鏈表實現的,在插入元素過程中,不需要擴容,內存分配效率很高
• Golang版本代碼,deque用的slice切片,在append過程中,不斷的擴容,進行內存分配,導致效率低
• 有興趣的朋友可以在此處優化deque這個數據結構,采用struct對象,構建雙向鏈表結構,相信,效率和Java版本的應該差不多,在此,篇幅限制,雙向鏈表也不是該算法的核心,筆者就到此為止
• 數據結構作為數據的存儲容易,對算法的影響也是巨大的

GitHub

• 項目源碼在這里
• 筆者會一直維護該項目,對leetcode中的算法題進行解決,并寫下自己的思路和見解,致力于人人都能看懂的算法

個人公眾號

• 喜歡的朋友可以關注,謝謝支持
• 記錄90后碼農的學習與生活

總結

以上是生活随笔為你收集整理的LeetCode算法系列_0862_和至少为K的最短子数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。