前缀和与哈希表求解连续子数组问题_前缀和 连续子数组

前缀和

前缀和是指一个数组中，从第一个元素开始到当前位置的所有元素的和。换句话说，前缀和是通过不断累加数组元素来计算得到的一个新数组。例如，对于数组 [1, 2, 3, 4, 5]，其前缀和为 [1, 3, 6, 10, 15]，即第一个元素为自身，后续元素为前一个元素与当前元素的和。

前缀和在解决一些问题时非常有用，例如计算连续子数组的和、查找某个范围内的和等。通过使用前缀和，可以在 O(1) 的时间复杂度内得到任意连续子数组的和，而不需要进行遍历求和。

需要注意的是，前缀和需要额外的空间来存储计算结果也就是需要额外的一个数组或者表去存储数据，因为需要获取到连续数组的具体坐标，所以可以将前缀累加后存入哈希表中，在实际应用中需要根据具体情况来判断是否使用前缀和。

哈希表（Hash Table）

也称为散列表，是一种常见的数据结构，用于快速存储和查找键值对。它通过将键映射到一个固定长度的数组索引来实现高效的查找操作。

在哈希表中，键经过哈希函数的计算后得到一个索引值，然后将键值对存储在该索引对应的位置上。当需要查找一个键时，先通过哈希函数计算出该键对应的索引，然后在该索引处寻找对应的值。

哈希表的优点是查找操作的平均时间复杂度为 O(1)，即常数时间。

这里有几个具体问题可供参考：

1. 和为K的连续子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
https://leetcode-cn.com/problems/subarray-sum-equals-k/

示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
 
提示：
1 <= nums.length <= 2 * 10**4
-1000 <= nums[i] <= 1000
-10**7 <= k <= 10**7
1
2
3
4
5
6
7
8
9
10
11

一种是可以暴力求解，通过不断循环遍历与枚举获得全部的子数组
时间复杂度是O（n^ 2）计算所有各种组合的部分和S[j,i]，考虑到计算S[j,i]的复杂度也是O(n)，所以总时间复杂度是O(n^3).因为在力扣上超时，这里不再演示代码过程。

另一种就是将前缀和逐一存入到哈希表中，由于只关心个数，而不关心j的实际值是什么，所以我们可以建立哈希表hashmap，以前缀和的值为key，该前缀和值出现的次数为value，每次哈希表中出现前缀和减去k的值存在于哈希表中时，便可以认为k这个值是hashmap[j-i]的值，也就是所要求的k，这样我们在考察子数组结束位置为i的情况时，只要查询hashmap[pre[i]-key]即可用O(1)的复杂度查询出结束位置为i的满足“其和为k”条件的子数组个数。

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/238572/he-wei-kde-zi-shu-zu-by-leetcode-solution/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.统计优美子数组

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。统计优美子数组的方法可以使用前缀和来进行计数，其中哈希表中存放的是奇数出现的次数
具体可以参考这张图，原文链接：https://blog.csdn.net/m0_38055352/article/details/105653923
图中一共有三个数组，其中①是原始数组a，②是前缀和数组pre，③是计次数组cnt。pre[i]表示截止i之前，共有多少个奇数，cnt[i]表示pre[i]出现了几次。

我们可以这样考虑，有了pre数组之后，假设[j, i]是一个优美子数组，那么其一定满足: pre[i] - pre[j-1] = k，那么我们如果想知道以第i个数作为结尾，共有多少个优美子数组，其实只需要求解pre[j-1] = pre[i] - k共出现了多少次即可，但是如果单纯的遍历，会造成O(n^2)的复杂度，这里就可以使用计次数组去把它化简为O(n)，其实就是把查找从O(n)简化为了O(1)。

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        
        if (nums.length == 0) {
            return 0;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        //统计奇数个数，相当于我们的 presum
        int oddnum = 0;
        int count = 0;
        map.put(0,1);
        for (int x : nums) {
            // 统计奇数个数
            oddnum += x & 1;
            // 发现存在，则 count增加
            if (map.containsKey(oddnum - k)) {
             count += map.get(oddnum - k);
            }
            //存入
            map.put(oddnum,map.getOrDefault(oddnum,0)+1);
        }
        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
24

3.平均数为k的最长连续子数组

题目要求：

给定n个正整数组成的数组，求平均数正好等于 k的最长连续子数组的长度。

输入描述：
第一行输入两个正整数n和k，用空格隔开。
第二行输入n个正整数a_i，用来表示数组。

输出描述：
如果不存在任何一个连续子数组的平均数等于k，则输出-1。
否则输出平均数正好等于 k 的最长连续子数组的长度。
示例1
输入例子：
5 2
1 3 2 4 1
输出例子：
3
例子说明：
取前三个数即可，平均数为2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个属于是更为经典的前缀和与哈希表的结合求解问题，其中可以将前缀和存放于哈希表的key中，value存放数组下标，将输入数组中的元素减去k可将题目转化为“和为0的最长连续子数组”。
若前缀和未存在于哈希表则将其与下标一同存储，若存在于哈希表中，则说明从哈希表存在位置到目前的位置通过加减得到相同的平均数即为目标数k，则下标相减就是连续子数组的长度，通过遍历进行比较得到最长的连续子数组。

public class day01 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long pre = 0, cur;
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 0);
        int ans = -1;
        for (int i = 1; i <= n; i++) {
            cur = pre + sc.nextInt() - k;
            if (map.containsKey(cur)) ans = Math.max(ans, i - map.get(cur));
            else map.put(cur, i);
            pre = cur;
        }
        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18