- [0560.subarray-sum-equals-k](./problems/560.subarray-sum-equals-k.en.md) ✅

- [Data Structure](./thinkings/basic-data-structure-en.md)✅

- [Basic Algorithm](./thinkings/basic-algorithm-en.md)✅

- [Dynamic Programming](./thinkings/dynamic-programming-en.md)✅

- [Huffman Encode and Run Length Encode](./thinkings/run-length-encode-and-huffman-encode-en.md)✅

- [Bloom Filter](./thinkings/bloom-filter-en.md)✅

- [String Problems](./thinkings/string-problems-en.md)✅

- [Sliding Window Technique](./thinkings/slide-window.en.md)✅

这道题目要我们求解连续的 n 个数中乘积最大的积是多少。这里提到了连续，笔者首先想到的就是滑动窗口，但是这里比较特殊，我们不能仅仅维护一个最大值，因此最小值（比如-20）乘以一个比较小的数（比如-10）

前面说了`最小值（比如-20）乘以一个比较小的数（比如-10）可能就会很大` 。因此我们需要同时记录乘积最大值和乘积最小值，然后比较元素和这两个的乘积，去不断更新最大值。当然，我们也可以选择只取当前元素。因此实际上我们的选择有三种，而如何选择就取决于哪个选择带来的价值最大（乘积最大或者最小）。

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经30K star啦。

大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解

The simplest method is `Brute-force`. Consider every possible subarray, find the sum of the elements of each of those subarrays and check for the equality of the sum with `k`. Whenever the sum equals `k`, we increment the `count`. Time Complexity is O(n^2). Implementation is as followed.

class Solution:

def subarraySum(self, nums: List[int], k: int) -> int:

cnt, n = 0, len(nums)

for i in range(n):

for j in range(i, n):

if (sum(nums[i:j + 1]) == k): cnt += 1

return cnt

If we implement the `sum()` method on our own, we get the time of complexity O(n^3).

class Solution:

def subarraySum(self, nums: List[int], k: int) -> int:

cnt, n = 0, len(nums)

for i in range(n):

for j in range(i, n):

sum = 0

for x in range(i, j + 1):

sum += nums[x]

if (sum == k): cnt += 1

return cnt

At first glance I think "maybe it can be solved by using the sliding window technique". However, I give that thought up when I find out that the given array may contain negative numbers, which makes it more complicated to expand or narrow the range of the sliding window. Then I think about using a prefix sum array, with which we can obtain the sum of the elements between every two indices by subtracting the prefix sum corresponding to the two indices. It sounds feasible, so I implement it as followed.

class Solution:

def subarraySum(self, nums: List[int], k: int) -> int:

cnt, n = 0, len(nums)

pre = [0] * (n + 1)

for i in range(1, n + 1):

pre[i] = pre[i - 1] + nums[i - 1]

for i in range(1, n + 1):

for j in range(i, n + 1):

if (pre[j] - pre[i - 1] == k): cnt += 1

return cnt

Actually, there is a more clever way to do this. Instead of using a prefix sum array, we use a hashmap to reduce the time complexity to O(n).

Algorithm:

- We make use of a hashmap to store the cumulative sum `acc` and the number of times the same sum occurs. We use `acc` as the `key` of the hashmap and the number of times the same `acc` occurs as the `value`.

- We traverse over the given array and keep on finding the cumulative sum `acc`. Every time we encounter a new `acc` we add a new entry to the hashmap. If the same `acc` occurs, we increment the count corresponding to that `acc` in the hashmap. If `acc` equals `k`, obviously `count` should be incremented. If `acc - k` got, we should increment `account` by `hashmap[acc - k]`.

- The idea behind this is that if the cumulative sum upto two indices is the same, the sum of the elements between those two indices is zero. So if the cumulative sum upto two indices is at a different of `k`, the sum of the elements between those indices is `k`. As `hashmap[acc - k]` keeps track of the number of times a subarray with sum `acc - k` has occured upto the current index, by doing a simple substraction `acc - (acc - k)` we can see that `hashmap[acc - k]` actually also determines the number of times a subarray with sum `k` has occured upto the current index. So we increment the `count` by `hashmap[acc - k]`.

Here is a graph demonstrating this algorithm in the case of `nums = [1,2,3,3,0,3,4,2], k = 6`.


When we are at `nums[3]`, the hashmap is as the picture shows, and `count` is 2 by this time. `[1, 2, 3]` accounts for one of the count, and `[3, 3]` accounts for another.

The subarray `[3, 3]` is obtained from `hashmap[acc - k]`, which is `hashmap[9 - 6]`.

- Prefix sum array

- Make use of a hashmap to track cumulative sum and avoid repetitive calculation.

*JavaScript Code*

var subarraySum = function (nums, k) {

const hashmap = {};

let acc = 0;

let count = 0;

for (let i = 0; i < nums.length; i++) {

acc += nums[i];

if (acc === k) count++;

if (hashmap[acc - k] !== void 0) {

count += hashmap[acc - k];

}

if (hashmap[acc] === void 0) {

hashmap[acc] = 1;

} else {

hashmap[acc] += 1;

}

}

return count;

};

*Python Cose*

class Solution:

def subarraySum(self, nums: List[int], k: int) -> int:

d = {}

acc = count = 0

for num in nums:

acc += num

if acc == k:

count += 1

if acc - k in d:

count += d[acc-k]

if acc in d:

d[acc] += 1

else:

d[acc] = 1

return count

There is a similar but a bit more complicated problem. Link to the problem: [437.path-sum-iii](https://github.com/azl397985856/leetcode/blob/master/problems/437.path-sum-iii.md)(Chinese).

- [LeetCode Sliding Window Series Discussion](https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/)（English）