[Swift]LeetCode862.和至少为K的最短子数组|ShortestSubarraywithSumatLeastK ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10595590.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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
Output: 1

Example 2:

Input: A = 4
Output: -1

Example 3:

Input: A = 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,2], K = 4
输出：-1

示例 3：

输入：A = [2,-1,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.max
11         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 : res
23     }
24 }
25 
26 struct Deque<T> {
27     var head = 0
28     var tail = 0
29     var arr = [T]()
30     
31     mutating func push(_ val: T) {
32         arr.append(val)
33         tail += 1
34     }
35     
36     @discardableResult mutating func popBack() -> T {
37         let val = arr.removeLast()
38         tail -= 1
39         return val
40     }
41     
42     @discardableResult mutating func popHead() -> T {
43         let val = arr[head]
44         head += 1
45         return val
46     }
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 == tail
58     }
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 : -1
25     }
26 }