LeetCode560. 和为K的子数组

思路

首先想到的是暴力求解，双重循环得出所有连续子串，但是多半要超时。没想到其他办法。看了题解，学到了前缀和的概念，这里的子串和等于end的前缀和减去start的前缀和。在前缀和的基础上，结合了hash来优化，也就是两数之和那道题。

两个地方需要注意。一、需要的前缀和可能出现多次，那么每次都得算上。二、前缀和为0也是一种情况，并且是必要的，需要手动添加。例如目标为0。

题目

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

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

复制

说明 :

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

Related Topics

• 数组
• 哈希表
• 前缀和
• 1078
• 0

代码

        public int subarraySum(int[] nums, int k) {

            // key前缀和，value出现的次数
            Map<Integer, Integer> qzh = new HashMap<>(nums.length);
            // 子串长度为0（在母串最前面），前缀和为0，出现次数+1（原本为0）
            qzh.put(0, 1);
            // 前缀和
            int sum = 0;
            int res = 0;

            for (int num : nums) {
                sum += num;
                // 找出需要的前缀和
                final Integer target = qzh.get(sum - k);
                if (target != null) {
                    res += target;
                }
                // 保存当前前缀和出现的次数
                qzh.put(sum, qzh.getOrDefault(sum, 0) + 1);
            }
            return res;
        }

复制

Post Views: 157