LeetCode 560. Subarray Sum Equals K

[Woodyiiiiiii]

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

* The length of the array is in range [1, 20,000].
* The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

---

这题求的是子数组内元素之和为指定k值的个数。

首先想到的是遍历所有可能的子数组，最简便的方法是暴力遍历：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0, sum = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            sum = 0;
            for (int j = i; j < n; ++j) {
                sum += nums[j];
                if (sum == k) ++res;
            }
        }
        return res;
    }
}

接下来，既然题目与累加和有关，我们可以联想到设计一个累加数组sums，sums[i] - sums[[j]的值就是i到j的子数组的累加和。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0, sum = 0, n = nums.length;
        int[] sums = nums.clone();
        if (sums[0] == k) ++res;
        for (int i = 1; i < n; ++i) {
            sums[i] = nums[i] + sums[i - 1];
            if (sums[i] == k) ++res;
            for (int j = 0; j < i; ++j) {
                if (sums[i] - sums[j] == k)
                    ++res;
            }
        }
        return res;
    }
}

然而这种解法跟暴力遍历没什么很大的区别，只不过是用线性空间存储了累加值而已，时间复杂度没有被优化。

为了继续减少时间复杂度，从“存储+累加和”的角度，我们可以联想到利用哈希表代替数组来存储累加和值，那么如何避免陷入上述数组的两层循环思路呢？我们可以利用题目已给的k值，判断是否存在sums[i] - k(显然数组是无法在O(1)的时间内进行判断的)，如果是，value值存储的是出现的次数，加入进结果变量res中。
注意一开始我们要存入(0, 1)，因为sums[i]本身也有可能等于k值。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0, sum = 0, n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                res += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

---

类似题目：

• 238. Product of Array Except Self
• 1. Two Sum
• 523. Continuous Subarray Sum

参考资料：

• https://leetcode.com/problems/subarray-sum-equals-k/
• [LeetCode] 560. Subarray Sum Equals K grandyang/leetcode#560
• https://leetcode.com/problems/subarray-sum-equals-k/discuss/645639/JAVA-Video-Explanation-w-code