剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例 1：
输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2：
输入:nums = [1,2,3], k = 3
输出: 2

提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/QTMn0o
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

最初想的是滑动窗口、或者暴力，后面觉得前缀和貌似效率更高。

我们并不需要构建一个数组来记录前缀和，只用维护一个变量sum，遍历数组时对sum进行更新，同时用一个map记录sum出现的次数。类似于力扣第一题两数之和，我们每次遍历时，都判断map中是否存在sum-k，存在则说明上一次出现sum的下标到遍历本次时的连续子数组和为k，记录出现sum-k的次数即可。

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 前缀和，map记录前i个数和以及出现次数
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int res = 0;
        // 记录前缀和
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // map存在sum - k，及说明存在i之前某一位置到i连续子数组和为k
            if (map.containsKey(sum - k)) {
                res += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return res;
    }
}

结果如下：

剑指 Offer II 011. 0 和 1 个数相同的子数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

提示：
1 <= nums.length <= 105
nums[i] 不是 0 就是 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/A1NYOS
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

和上一道题一样，也是前缀和+哈希表，注释已经写的很清楚了。这里说一下初始入map，没有元素时前缀和为0，但它的下边为-1，是为了后续计算子数组长度时用当前下标减去-1即可，就不用像计算普通长度时是j - i + 1。

用变量sum记录前缀和，遇见1加1，遇见0减1，这样保证下一次当前缀和为sum且map中存在sum时，构成的子数组经过+相同数量的1和-相同数量的1，则代表子数组中有相同数量的0和1，对比长度即可。

class Solution {
    public int findMaxLength(int[] nums) {
        int res = 0;
        // 记录前缀和
        int sum = 0;
        // 记录前缀和及下标
        Map<Integer, Integer> map = new HashMap<>();
        // 记录初始前缀和
        map.put(0, -1);

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            // 为1加1，为0减1
            if (num == 1) sum++;
            else sum--;

            // 如果map包含sum，及证明第一次出现sum的下标到此时sum组成的连续子数组包含相同0和1
            if (map.containsKey(sum)) {
                res = Math.max(res, i - map.get(sum));
            } else {
                // 仅记录第一次前缀和出现的下标，不更新后续出现位置
                map.put(sum, i);
            }
        }
        
        return res;
    }
}

结果如下：