[Swift]LeetCode862. 和至少为 K 的最短子数组 | Shortest Subarray with Sum at Least K

概述Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K. If there is no non-empty subarray with sum at least K, return -1. Example 1: Input: A = [1], K = 1 Output: 1

Return the length of the shortest,non-empty,contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K,return -1.

Example 1:

input: A = [1],K = 1 Output: 1 

Example 2:

input: A = [1,2],K = 4 Output: -1 

Example 3:

input: A = [2,-1,K = 3 Output: 3

Note:

1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1 。

 示例 1：

输入：A = [1],K = 1输出：1

示例 2：

输入：A = [1,K = 4输出：-1

示例 3：

输入：A = [2,K = 3输出：3 

提示：

1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9 956ms

 

 1 class Solution { 2     func shortestSubarray(_ A: [Int],_ K: Int) -> Int { 3         var prefixSums = [Int]() 4         prefixSums.append(0) 5         var sum = 0 6         for (i,num) in A.enumerated() { 7             sum += num 8             prefixSums.append(sum) 9         }10         var res = Int.max11         var deque = Deque<(Int,Int)>()12         for i in 0..<prefixSums.count {13             while !deque.isEmpty && deque.back.0 >= prefixSums[i] {14                 deque.popBack()15             }16             deque.push( (prefixSums[i],i) )17             while !deque.isEmpty && prefixSums[i] - deque.front.0 >= K {18                 res = min(res,i - deque.front.1)19                 deque.pophead()20             }21         }22         return res == Int.max ? -1 : res23     }24 }25 26 struct Deque<T> {27     var head = 028     var tail = 029     var arr = [T]()30     31     mutating func push(_ val: T) {32         arr.append(val)33         tail += 134     }35     36     @discardableResult mutating func popBack() -> T {37         let val = arr.removeLast()38         tail -= 139         return val40     }41     42     @discardableResult mutating func pophead() -> T {43         let val = arr[head]44         head += 145         return val46     }47     48     var front: T {49         return arr[head]50     }51     52     var back: T {53         return arr[tail - 1]54     }55     56     var isEmpty: Bool {57         return head == tail58     }59 }

Runtime: 1240 ms Memory Usage: 20.6 MB

 1 class Solution { 2     func shortestSubarray(_ A: [Int],_ K: Int) -> Int { 3         var N:Int = A.count 4         var res:Int = N + 1 5         var B:[Int] = [Int](repeating:0,count:N + 1) 6         for i in 0..<N 7         { 8             B[i + 1] = B[i] + A[i] 9         }10         var d:[Int] = [Int]()11         for i in 0..<(N + 1)12         {13             while (d.count > 0 && B[i] - B[d.first!] >= K)14             {15                 res = min(res,i - d.first!)16                  d.removeFirst()17             }18             while (d.count > 0 && B[i] <= B[d.last!])19             {20                 d.popLast()21             }22             d.append(i)23         }24         return res <= N ? res : -125     }26 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode862. 和至少为 K 的最短子数组 | Shortest Subarray with Sum at Least K全部内容，希望文章能够帮你解决[Swift]LeetCode862. 和至少为 K 的最短子数组 | Shortest Subarray with Sum at Least K所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。