LeetCode算法心得——和为k的子数组（前缀和+HashMap）

大家好，我是晴天学长，这是一个很重要的前缀和+hash运用的题，为后面很多的题打基础，需要的小伙伴可以关注支持一下哦！后续会继续更新的。

---

1) .和为k的子数组

题目描述：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。 子数组是数组中元素的连续非空序列。
示例 1：

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

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

---

2) .算法思路

暴力法

解析

我们先来用暴力法解决这个题目，很简单，一下就能 AC。

这个题目的题意很容易理解，就是让我们返回和为 k 的子数组的个数，所以我们直接利用双重循环解决该题，这个是很容易想到的。我们直接看代码吧。

class Solution {
    public int subarraySum(int[] nums, int k) {
         int len = nums.length;
         int sum = 0;
         int count = 0;
         //双重循环
         for (int i = 0; i < len; ++i) {
             for (int j = i; j < len; ++j) {
                 sum += nums[j];
                 //发现符合条件的区间
                 if (sum == k) {
                     count++;
                 }
             }
             //记得归零，重新遍历
             sum = 0;
         }
         return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

好啦，既然我们已经知道如何求前缀和数组了，那我们来看一下如何用前缀和思想来解决这个问题。

class Solution {
    public int subarraySum(int[] nums, int k) {
        //前缀和数组
        int[] presum = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            //这里需要注意，我们的前缀和是presum[1]开始填充的
            presum[i+1] = nums[i] + presum[i];
        }
        //统计个数
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i; j < nums.length; ++j) {
                //注意偏移，因为我们的nums[2]到nums[4]等于presum[5]-presum[2]
                //所以这样就可以得到nums[i,j]区间内的和
                if (presum[j+1] - presum[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

我们分析上面的代码，发现该代码虽然用到了前缀和数组，但是对比暴力法并没有提升性能，时间复杂度仍为O(n^2)，空间复杂度成了 O(n)。那我们有没有其他方法解决呢？

前缀和 + HashMap

了解这个方法前，我们先来看一下下面这段代码，保证你很熟悉

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer,Integer> map  = new HashMap<>();
        //一次遍历
        for (int i = 0; i < nums.length; ++i) {
            //存在时，我们用数组得值为 key，索引为 value
            if (map.containsKey(target - nums[i])){              
               return new int[]{i,map.get(target-nums[i])};
            }
            //存入值
            map.put(nums[i],i);
        }
        //返回
        return new int[]{};
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

上面的这段代码是不是贼熟悉，没错就是那个快被我们做烂的两数之和。这一段代码就是用到了我们的前缀和+ HashMap 思想，那么我们如何通过这个方法来解决这个题目呢？

在上面的代码中，我们将数组的值和索引存入 map 中，当我们遍历到某一值 x 时，判断 map 中是否含有 target - x，即可。

---

3) .算法步骤

1.创建一个HashMap对象 map 用于存储前缀和与对应出现次数的映射关系。
2.初始化变量 answer 为0，表示符合条件的子数组个数。
3.检查第一个元素是否等于k，如果是，则 answer 加1，表示该元素本身就是一个满足条件的子数组。
将第一个元素和对应的出现次数放入 map 中。
4.使用一个循环遍历数组中的元素，从第二个元素开始。
5.将当前元素的值加上前一个元素的值，即求得当前位置的前缀和。
6.检查当前前缀和是否等于k，如果是，则 answer 加1。
7.检查 map 中是否包含前缀和减去k的值，如果是，则将对应的出现次数加到 answer 中。
8.将当前前缀和和对应的出现次数放入 map 中，更新映射关系。
9.循环结束后，返回 answer，表示满足条件的子数组个数。

---

4）.代码示例

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
            int answer = 0;
            //S[R] = S[L]+K;
            answer += k == nums[0] ? 1 : 0;
            map.put(nums[0], map.getOrDefault(nums[0], 0) + 1);
            for (int i = 1; i < nums.length; i++) {
                nums[i] += nums[i - 1];
                answer+=nums[i]==k?1:0;
                if (map.containsKey(nums[i] - k)) {
                    answer+=map.get(nums[i] - k);
                }
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
            return answer;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

5）.总结

• Hash和前缀和的正确使用。

---

试题链接：