題目

給你一個整數數組 nums 和一個整數 k ，請你統計并返回 該數組中和為 k 的子數組的個數 。

子數組是數組中元素的連續非空序列。

數據范圍

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

樣例

示例 1：

輸入：nums = [1,1,1], k = 2
輸出：2

示例 2：

輸入：nums = [1,2,3], k = 3
輸出：2

題解

博主的o(n²)方思路，還是太菜了，離最最優解就差一步！！

public int subarraySum(int[] nums, int k) {int res=0;int len=nums.length;int sum[]=new int[len];sum[0]=nums[0];//前綴和for(int i=1;i<len;i++){sum[i]=sum[i-1]+nums[i];}//遍歷for(int i=0;i<len;i++){for(int j=i;j<len;j++){int t;if(i-1>=0) {t= sum[j] - sum[i - 1];}else{t =sum[j];}if(t==k) res++;}}return res;}

官方題解（前綴和+哈希 O（n））

public class Solution {public int subarraySum(int[] nums, int k) {int count = 0;for (int start = 0; start < nums.length; ++start) {int sum = 0;for (int end = start; end >= 0; --end) {sum += nums[end];if (sum == k) {count++;}}}return count;}
}作者：力扣官方題解
鏈接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/238572/he-wei-kde-zi-shu-zu-by-leetcode-solution/
來源：力扣（LeetCode）

思路

這道題整體來說不難，因為我們觀察數據量，只有2*10⁴,那么即使O（n²）的時間復雜度也能通過，也就是說遍歷也能通過。但我們肯定追求更短的時間復雜度，首先，根據提議，知道我們是計算數組中一段連續子數組的和。想到數組中連續數據的和，我們應當首先想到前綴和，經過O(n)的預處理后，每一個連續子區間的值都可以在O（1）的時間復雜度內求出。

然后博主就止步于此了TWT。

官方題解確實很巧妙，在使用前綴和的前提下，做進一步思考，對前綴和式子做一點小小的轉換。

我們將p[i] -p[j-1]==k的判斷式 改為 p[j-1]=pre[i]-k；

我們再進一步轉換思路，得到這樣的式子后，我們是否可以提前哈希處理前綴和數組每一個數值，并存儲每一個數值的數量，那么我們遍歷一遍前綴和數組，根據表達式，我們通過哈希找到符合條件p[j-1]的數目即可。

這類處理方法只能說大家和博主一起多多積累經驗，有了經驗才能一通百通。