題目敘述
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Constraints:
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
Hint 1:
Will Brute force work here? Try to optimize it.
Hint 2:
Can we optimize it by using some extra space?
Hint 3:
What about storing sum frequencies in a hash table? Will it be useful?
Hint 4:
sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1. Can we use this property to optimize it.
題目翻譯
這題是要找出在 nums 中的子陣列其元素是可以加總起來相當於 k 的組合。例如範例一，
[1, 1, 1] 可以符合 k=2 的組合是 [1, 1, 1] 和 [1, 1, 1]。
解法解析
這題的解法是使用了 Hash Map 來處理，其 Time complexity 是最好的只有 O(n)，雖然 Space complexity 只能到 O(n)，但是如果要讓 Space complexity 降到 O(1) 的解法，卻會讓 Time complexity 漲到 O(n^2)，實在不是一個划算的交易。
解題的概念是：
- 如果從索引 0 到索引 i 的總和和到索引 j 的總和相同，代表索引 i 到索引 j 的總和是 0。
sum[i] + nums[i+1] + nums[i+...] = sum[j] 代表 nums[i+1] + nums[i+...] = 0
- 如果
sum[i] - sum[j] = k，代表 nums[i+1] + nums[i+...] = k
依照此概念，使用 hash map 去儲存所有的 sum[i] 出現過的次數，並且判斷 sum[i] - sum[j] = k 的總次數，就會是答案。
程式範例
Go
func subarraySum(nums []int, k int) int {
count := 0
sum := 0
m := map[int]int{
0: 1,
}
for _, num := range nums {
sum += num
if val, ok := m[sum-k]; ok {
count += val
}
m[sum]++
}
return count
}
JavaScript
var subarraySum = function (nums, k) {
let count = 0,
sum = 0;
const map = new Map([[0, 1]]);
for (const num of nums) {
sum += num;
count += map.get(sum - k) || 0;
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
};
Kotlin
class Solution {
fun subarraySum(nums: IntArray, k: Int): Int {
var count = 0
var sum = 0
val map: HashMap<Int, Int> = hashMapOf(0 to 1)
for (num in nums) {
sum += num
count += map.getOrDefault(sum - k, 0)
map[sum] = map.getOrDefault(sum, 0) + 1
}
return count
}
}
PHP
class Solution
{
function subarraySum($nums, $k)
{
$count = 0;
$sum = 0;
$map = [0 => 1];
foreach ($nums as $num) {
$sum += $num;
if (isset($map[$sum - $k])) {
$count += $map[$sum - $k];
}
$map[$sum] = isset($map[$sum]) ? $map[$sum] + 1 : 1;
}
return $count;
}
}
Python
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count, amount = 0, 0
hash_map = {0: 1}
for num in nums:
amount += num
count += hash_map.get(amount - k, 0)
hash_map[amount] = hash_map.get(amount, 0) + 1
return count
Rust
impl Solution {
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
let mut sum = 0;
let mut count = 0;
let mut map = std::collections::HashMap::new();
map.insert(0, 1);
for num in nums {
sum += num;
if let Some(v) = map.get(&(sum - k)) {
count += v;
}
*map.entry(sum).or_insert(0) += 1;
}
return count;
}
}
Swift
class Solution {
func subarraySum(_ nums: [Int], _ k: Int) -> Int {
var count = 0
var sum = 0
var map: [Int:Int] = [0:1]
for num in nums {
sum += num
count += map[sum - k, default: 0]
map[sum, default: 0] += 1
}
return count
}
}