力扣560. 和为 K 的子数组

Problem: 560. 和为 K 的子数组
  
  
题目描述

   

  思绪

   1.初始化一个哈希表preSum，用于记录前缀和及其出现次数,ans记录和为k的子数组数目、sum_i记录当前前缀和；
2.将前缀和为 0 的情况存入哈希表，表示前缀和为 0 出现了一次。;
3.对数组 nums 进行遍历，计算当前的前缀和 sum_i。计算当前前缀和减去 k 的值 sum_j，以此检查是否存在从某个位置到当前位置的子数组和为 k。
4.假如 sum_j 存在于哈希表中，说明存在某个位置到当前位置的子数组和为 k，将其出现的次数累加到 ans 中。将当前前缀和 sum_i 存入哈希表，并记录其出现次数。
  复杂度

时间复杂度:
                                           O                            (                            n                            )                                  O(n)                     O(n);其中                                        n                                  n                     n为数组的长度
  空间复杂度:
                                           O                            (                            n                            )                                  O(n)                     O(n)
  Code

1. class Solution {
2.     /**
3.      * Subarray Sum Equals K
4.      *
5.      * @param nums Given array
6.      * @param k    Given number
7.      * @return int
8.      */
9.     public int subarraySum(int[] nums, int k) {
10.         int n = nums.length;
11.         // Use HashMap to record the prefix and its occurrence
12.         //map< prefix sum, number of occurrences of the prefix sum >
13.         Map<Integer, Integer> preSum = new HashMap<>();
14.         preSum.put(0, 1);
15.         int ans = 0, sum_i = 0;
16.         // sum[j] and sum[i] -k are equal
17.         for (int i = 0; i < n; i++) {
18.             sum_i += nums[i];
19.             // prefix and nums[0....j]
20.             int sum_j = sum_i - k;
21.             // If sum_j exists, update the answer
22.             if (preSum.containsKey(sum_j)) {
23.                 ans += preSum.get(sum_j);
24.             }
25.             preSum.put(sum_i, preSum.getOrDefault(sum_i, 0) + 1);
26.         }
27.         return ans;
28.     }
29. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。