[Swift]LeetCode560. 和为K的子数组 | Subarray Sum Equals K

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

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2 Output: 2 

Note:

The length of the array is in range [1, 20,000].The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

---

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

---

56ms

1 class Solution { 2 func subarraySum(_ nums: [Int], _ k: Int) -> Int { 3 if nums.count == 0 { 4 return 0 5 } 6 var dic : Dictionary<Int, Int> = [:] 7 var sum : Int = 0; 8 var res : Int = 0; 9 for i in 0 ..< nums.count { 10 sum += nums[i] 11 12 if sum == k { 13 res += 1 14 } 15 16 if dic[sum - k] != nil { 17 res += dic[sum - k]! 18 } 19 20 if dic[sum] == nil { 21 dic[sum] = 1 22 } else { 23 dic[sum] = dic[sum]! + 1 24 } 25 } 26 return res 27 } 28 }

---

120ms

1 class Solution { 2 func subarraySum(_ nums: [Int], _ k: Int) -> Int { 3 var sumCounter = [0: 1] 4 var s = 0, res = 0 5 for i in 0..<nums.count { 6 s += nums[i] 7 res += sumCounter[s - k] ?? 0 8 sumCounter[s, default: 0] += 1 9 } 10 return res 11 } 12 }

---

Runtime: 124 ms Memory Usage: 19.8 MB 1 class Solution { 2 func subarraySum(_ nums: [Int], _ k: Int) -> Int { 3 var res:Int = 0 4 var sum:Int = 0 5 var n:Int = nums.count 6 var m:[Int:Int] = [0:1] 7 for i in 0..<n 8 { 9 sum += nums[i] 10 res += m[sum - k,default:0] 11 m[sum,default:0] += 1 12 } 13 return res 14 } 15 }

---

124ms

1 class Solution { 2 func subarraySum(_ nums: [Int], _ k: Int) -> Int { 3 4 guard nums.count > 0 else { return -1 } 5 var count = 0 6 var sum = 0 7 8 var dictionary: [Int: Int] = [:] 9 dictionary[0] = 1 10 for i in 0..<nums.count { 11 sum += nums[i] 12 if let occurance = dictionary[sum - k] { 13 count += occurance 14 } 15 16 if let occurance = dictionary[sum] { 17 dictionary[sum] = occurance + 1 18 } else { 19 dictionary[sum] = 1 20 } 21 22 } 23 24 return count 25 } 26 }

---

148ms

1 class Solution { 2 func subarraySum(_ nums: [Int], _ k: Int) -> Int { 3 var partialSums = [Int: [Int]]() 4 partialSums[0] = [0] 5 var found = [(Int, Int)]() 6 var sum = 0 7 for (i, num) in nums.enumerated() { 8 sum += num 9 if let bounds = partialSums[sum - k] { 10 bounds.forEach { found.append(($0, i)) } 11 } 12 partialSums[sum, default: []].append(i) 13 } 14 return found.count 15 } 16 }

 

 

转载于:https://www.cnblogs.com/strengthen/p/10420094.html