題目描述

和為 K 的子數組

給定一個整數數組和一個整數 k ，請找到該數組中和為 k 的連續子數組的個數。
示例 1：
輸入:nums = [1,1,1], k = 2
輸出: 2
解釋: 此題 [1,1] 與 [1,1] 為兩種不同的情況
示例 2：
輸入:nums = [1,2,3], k = 3
輸出: 2
提示:
1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

算法原理和細節問題

解法（將前綴和存在哈希表中）：
算法思路：
設 i 為數組中的任意位置，? sum[i] 表? [0, i] 區間內所有元素的和。
想知道有多少個「以 i 為結尾的和為 k 的?數組」，就要找到有多少個起始位置為 x1, x2, x3… 使得 [x, i] 區間內的所有元素的和為 k 。那么 [0, x] 區間內的和是不是就是sum[i] - k 了。于是問題就變成：
? 找到在 [0, i - 1] 區間內，有多少前綴和等于 sum[i] - k 的即可。
我們不?真的初始化?個前綴和數組，因為我們只關?在 i 位置之前，有多少個前綴和等于sum[i] - k 。因此，我們僅需??個哈希表，?邊求當前位置的前綴和，?邊存下之前每?種前綴和出現的次數。

代碼

C++ 算法代碼：

class Solution
{
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> hash; // 統計前綴和出現的次數hash[0] = 1;int sum = 0, ret = 0;for(auto x : nums){sum += x; // 計算當前位置的前綴和if(hash.count(sum - k)) ret += hash[sum - k]; // 統計個數hash[sum]++;}return ret;}
}

Java 算法代碼：

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> hash = new HashMap<Integer, Integer>();hash.put(0, 1);int sum = 0, ret = 0;for(int x : nums){sum += x; // 計算當前位置的前綴和ret += hash.getOrDefault(sum - k, 0); // 統計結果hash.put(sum, hash.getOrDefault(sum, 0) + 1); // 把當前的前綴和丟到哈希表??}return ret;}
}

注：統計結果 和 把當前的前綴丟到哈希表里不能換順序
否則k=0時將不會輸出0