這道題主要是找規律，優化的時候可以利用哈希表和數組的特性。
原題
給定一個整數數組和一個整數 k，你需要找到該數組中和為 k 的連續的子數組的個數。
示例 1 :
<code>輸入:nums = [1,1,1], k = 2輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。/<code>
說明 :
- 數組的長度為 [1, 20,000]。
- 數組中元素的範圍是 [-1000, 1000] ，且整數 k 的範圍是 [-1e7, 1e7]。
原題url：https://leetcode-cn.com/problems/subarray-sum-equals-k/
解題
一開始的想法肯定就是利用暴力解法了，三層 for 循環的那種，第1層和第2層選擇起點和終點，第3層則是計算起點到終點的總和。這樣的想法最簡單，但很可惜，直接超時了，讓我們稍微優化一下。
子數組之和
因為題目要求子數組下標連續，那麼我們想想，如果要求sum(i, j)(也就是從下標 i 到下標 j 的子數組之和)，其實可以轉化成sum(0, i - 1) - sum(0, j)。這樣的話，就可以把上面的三層for循環優化成兩層。
接下來我們直接看看代碼：
<code>class Solution { public int subarraySum(int[] nums, int k) { // sum(i, j) = sum(0, j) - sum(0, i - 1) int[] sumArray = new int[nums.length]; sumArray[0] = nums[0]; for (int i = 1; i < nums.length; i++) { sumArray[i] = sumArray[i - 1] + nums[i]; } int result = 0; int sum = 0; for (int i = sumArray.length - 1; i >= 0; i--) { // 前i個數之和 if (sumArray[i] == k) { result++; } // 查詢從(j + 1)到i的和 for (int j = i - 1; j >= 0 && j != i; j--) { sum = sumArray[i] - sumArray[j]; if (sum == k) { result++; } } } return result; }}/<code>提交OK，但時間複雜度是O(n^2)，優化一下。
用哈希表優化
我們想想，上面使用使用第二層for循環，主要是為了查出 sumArray 中是否還存在等於sumArray[i] - k的數，這明顯是一個映射關係，因此我們用一個 map 去記錄中間的求和結果。
<code>class Solution { public int subarraySum(int[] nums, int k) { // sum(i, j) = sum(0, j) - sum(0, i - 1) // 用map存儲，key為sum，value為第i個數 Map<integer>> map = new HashMap<>(nums.length * 4 / 3 + 1); // 數組求和 int sum = 0; // 記錄一共有哪些和 Set<integer> sumSet = new HashSet<>(); for (int i = 0; i < nums.length; i++) { sum += nums[i]; sumSet.add(sum); // 查看當前是否已經記錄 List<integer> indexList = map.get(sum); if (indexList == null) { indexList = new LinkedList<>(); } indexList.add(i); map.put(sum, indexList); } int result = 0; for (Integer subSum : sumSet) { List<integer> list = map.get(subSum); // 如果list為null，說明是被移除了，說明之前已經計算過 if (list == null) { continue; } if (subSum == k) { result += map.get(subSum).size(); } // 剩餘的和 int remainSum = subSum - k; List<integer> remainList = map.get(remainSum); // 如果為null，說明不存在 if (remainList == null) { continue; } // 如果不為null，說明存在，則可以進行配對 // 讓list和remainList進行配對 for (int index1 : list) { for (int index2 : remainList) { if (index1 <= index2) { continue; } result++; } } } return result; }}/<integer>/<integer>/<integer>/<integer>/<integer>/<code>提交OK，雖然較之前的方法時間效率上有所提高，但並沒有本質區別。特別是最後的雙重 for 循環，因為下標只有大的減小的才有意義，這樣也就給自己額外增加了運算。
那麼反思一下，是否真的有必要提前算好子數組的和？如果一邊遍歷一邊求和，並將求和的結果存入map中，那麼 map 中存在的，一定是下標小於自己的求和結果。針對這點，我們可以再做一步優化：
<code>public class Solution { public int subarraySum(int[] nums, int k) { // 最終結果的數量 int count = 0; // 求和 int sum = 0; // key為中間求出了哪些和，value為當前和有幾種情況 HashMap<integer> map = new HashMap<>(); // 和為0有1中情況，就是一個數都不選 map.put(0, 1); // 遍歷數組 for (int i = 0; i < nums.length; i++) { // 求和 sum += nums[i]; // map中是否有記錄剩餘的值 if (map.containsKey(sum - k)) { // 累加，此處可以直接添加，是因為求和是從前往後進行的，現在能找到的，說明一定是之前的 count += map.get(sum - k); } // 記錄當前的值 map.put(sum, map.getOrDefault(sum, 0) + 1); } return count; }}/<integer>/<code>提交OK，這樣時間複雜度就變為了O(n)。
數據結構的優化
現在，我們用哈希表來存儲中間結果。雖然哈希表的查找效率理論上可以達到O(1)，但考慮到哈希衝突，最壞情況下還是有可能達到O(n)。真正能夠保證達到O(1)的數據結構，是數組（用空間換取時間）。
那這個用來存儲的一維數組究竟長度該設置為多少呢？自然就是找出數組中子數組之和的最大值和最小值，兩者求差，結果就是最終的數組長度。利用這個數組去存儲子數組求和的結果，這樣就能保證在查找時的效率了。
<code>class Solution { public int subarraySum(int[] nums, int k) { int sum = 0; // sum的最小值和最大值，因為可以一個數值都不選，因此0作為初始值 int min = 0; int max = 0; // 求和 for (int n : nums) { sum += n; min = Math.min(min, sum); max = Math.max(max, sum); } // sums[i]代表從下標為0到下標為i的子數組之和 // 用一個數組存儲，相比於map，取值更快，用空間換取時間 int[] sums = new int[max - min + 1]; // 最終結果 int count = 0; sum = 0; // 遍歷數組 // 需要重新求和，因為沒有類似set這樣的結構存儲了結果 for (int n : nums) { // 求和 sum += n; // 新的目標值 int target = sum - min - k; // 是否有超過範圍 if (target >= 0 && target < sums.length) { count += sums[target]; } sums[sum - min]++; } // 再加上本身就是k的子數組的數量 if (k - min >= 0 && k - min < sums.length) { count += sums[k - min]; } return count; }}/<code> 提交OK，執行時間上更快了。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要是找規律，優化的時候可以利用哈希表和數組的特性。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
閱讀更多 健程之道 的文章
