[Swift]LeetCode209.长度最小的子数组|MinimumSizeSubarraySum

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

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

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

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

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

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

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

20ms

 1 class Solution {
 2 func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
 3     guard nums.count > 0 else {
 4         return 0
 5     }
 6     var i = 0, j = 0,minX = nums.count, sum = nums[0], match = false
 7     while j < nums.count {
 8         if i == j {
 9             if sum < s {
10                 j = j + 1
11                 if j == nums.count {
12                     break;
13                 }
14                 sum = nums[j] + sum
15             } else {
16                 return 1
17             }
18         } else {
19             if sum < s {
20                 j = j + 1
21                 if j == nums.count {
22                     break
23                 }
24                 sum = nums[j] + sum
25             } else {
26                 match = true
27                 minX = min(j - i + 1, minX)
28                 sum = sum - nums[i]
29                 i = i + 1
30             }
31         }
32     }
33     return match ? minX : 0
34 }
35 }

24ms

 1 class Solution {
 2     func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
 3 
 4         var sum = 0, left = 0, res = Int.max
 5         for i in nums.indices {
 6             sum += nums[i]
 7             while sum >= s {
 8                 res = min(res, i-left+1)
 9                 sum -= nums[left]
10                 left += 1
11             }
12         }
13         return (res == Int.max) ? 0 : res
14     }
15 }

24ms

 1 class Solution {
 2     func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
 3         var miniSize = Int.max ,start = 0, currentSum = 0
 4         
 5         for (i, num) in nums.enumerated() {
 6             currentSum += num
 7             
 8             while currentSum >= s && start <= i {
 9                 miniSize = min(miniSize, i - start + 1)
10                 
11                 currentSum -= nums[start]
12                 start += 1
13             }
14         }
15         
16         return miniSize == Int.max ? 0 : miniSize
17     }
18 }

32ms

 1 class Solution {
 2     func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
 3         let n = nums.count
 4         if (n < 1 || nums.reduce(0, +) < s) { return 0 }
 5 
 6         // 维护一个滑动窗口 nums[i,j], nums[i...j] < s
 7         var i = 0
 8         var j = -1
 9         var total = 0
10         var res = n + 1
11         while i <= n-1 {
12             if (j + 1 < n) && total < s {   // 小于目标值
13                 j += 1
14                 total += nums[j]
15             } else {    // 大于目标值
16                 total -= nums[i]
17                 i += 1
18             }
19             if total >= s {
20                 res = min(res, j-i+1)   // 求得当前最小长度
21             }
22         }
23         if res == n+1 { // 没有改变过
24             return 0
25         }
26         return res
27     }
28 }

84ms

 1 class Solution {
 2     func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
 3         guard nums.count > 0 else {
 4             return 0
 5         }
 6         
 7         var sums : [Int] = [0]
 8         for num in nums{
 9             sums.append(sums.last! + num)
10         }
11         
12         var minCount : Int = Int.max
13         
14         for (index, sum) in sums.enumerated(){
15             if sum >= s{
16                 let key = sum - s
17                 var foundIndex = binarySearch(low: 0, high: sums.count - 1, key: key, sums: sums)
18                 if sums[foundIndex] > key{
19                     foundIndex -= 1
20                 }
21                 minCount = min(minCount, index - foundIndex)
22             }
23         }
24         
25          if sums.last! >= s{
26             return min(nums.count, minCount)
27         }else{
28             return 0 
29         }
30         
31     }
32     
33     func binarySearch(low : Int, high : Int, key : Int, sums : [Int])->Int{
34         guard low < high else{
35             return low
36         }
37         
38         let mid = (low + high) / 2
39         let value = sums[mid]
40         if value == key{
41             return mid
42         }else if value > key{
43             return binarySearch(low : low, high : mid-1, key : key, sums : sums)
44         }else{
45             return binarySearch(low : mid + 1, high : high, key : key, sums : sums)
46         }
47     }
48 }