本文题目难度标识：🟩简单，🟨中等，🟥困难。

前缀和

对于「连续子数组问题」一般可以通过前缀和方式解决。

题目：🟨 560. 和为 K 的子数组 - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

子数组是数组中元素的连续非空序列。

暴力枚举：

时间复杂度： $O(n^2)$ ，其中 n 为数组的长度。枚举子数组开头和结尾需要 $O(n^2)$ 的时间，其中求和需要 $O(1)$ 的时间复杂度，因此总时间复杂度为 $O(n^2)$ 。
空间复杂度： $O(1)$ 。只需要常数空间存放若干变量。

下面介绍前缀和 + 哈希表优化方法。

定义 pre[i] 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：pre[i]=pre[i−1]+nums[i]。

那么「[j..i] 这个子数组和为 k 」这个条件我们可以转化为 pre[i]−pre[j−1]==k。

因此我们可以在遍历的同时计算前缀和 pre[i] 时，找一下哈希表中有没有存有 pre[j−1] 即可。

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;
}

复杂度分析：

时间复杂度： $O(n)$ ，其中 n 为数组的长度。我们遍历数组的时间复杂度为 $O(n)$ ，中间利用哈希表查询删除的复杂度均为 $O(1)$ ，因此总时间复杂度为 $O(n)$ 。
空间复杂度： $O(n)$ ，其中 n 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，因此需要 $O(n)$ 的空间复杂度。

前缀「条件」和

我这里起名前缀「条件」和，是因为这里 nums 元素必须满足一定条件，才统计入前缀和。

题目：🟨 1248. 统计「优美子数组」 - 力扣（LeetCode）

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

请返回这个数组中「优美子数组」的数目。

本题和上题十分相像。与前缀和解法不同的是，我们定义的前缀数组累积的是符合特定条件（在本题里为奇数数字）的元素数目。

我们定义 pre[i] 为 [0..i] 中奇数的个数，则 pre[i] 可以由 pre[i−1] 递推而来，即：pre[i]=pre[i−1]+(nums[i]&1)。

那么「[j..i] 这个子数组里的奇数个数恰好为 k 」这个条件我们可以转化为 pre[i]−pre[j−1]==k。

因此我们可以在遍历的同时计算前缀和 pre[i] 时，找一下哈希表中有没有存有 pre[j−1] 即可。

public int numberOfSubarrays(int[] nums, int k) {
	int res = 0, pre = 0;
	HashMap < Integer, Integer > mp = new HashMap < > ();
	mp.put(0, 1); // 考虑到答案是整个前缀本身的情况
	for (int i = 0; i < nums.length; i++) {
		pre += nums[i]&1;
		if (mp.containsKey(pre - k)) {
			res += mp.get(pre - k);
		}
		mp.put(pre, mp.getOrDefault(pre, 0) + 1);
	}
	return res;
}

复杂度分析:

时间复杂度： $O(n)$ ，其中 n 为数组的大小。我们只需要遍历一遍数组即可求得答案。
空间复杂度： $O(n)$ ，其中 n 为数组的大小。哈希表在最坏情况下可能有 n 个不同的键值，因此需要 $O(n)$ 的空间复杂度。

前缀特征

所谓前缀特征指的就是 pre[i] 代表 nums[0] 到 nums[i] 中的一个特征值是多少。比如：

pre[i] 代表 nums[0] 到 nums[i] 中的最大值/最小值。
pre[i] 代表 nums[0] 到 nums[i] 中最后一次满足 xxx 条件的值。

从这里开始，动态规划的味道就开始上来了。

题目：🟨 795. 区间子数组个数 - 力扣（LeetCode）

给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

一个子数组的最大值范围在 [left,right] 表示子数组中不能含有大于 right 的元素，且至少含有一个处于 [left,right] 区间的元素。

我们可以将数组中的元素分为三类，并分别用 0, 1, 2 来表示：

小于 left，用 0 表示；
大于等于 left 且小于等于 right，用 1 表示；
大于 right，用 2 表示。

那么本题可以转换为求解不包含 2，且至少包含一个 1 的子数组数目。我们遍历 i，并将右端点固定在 i，求解有多少合法的子区间。过程中需要维护两个变量：

last1，表示上一次 1 出现的位置，如果不存在则为 −1；
last2，表示上一次 2 出现的位置，如果不存在则为 −1。

如果 last1 != −1，那么子数组若以 i 为右端点，合法的左端点可以落在 (last2,last1] 之间。这样的左端点共有 last1−last2个。

因此，我们遍历 i：

如果 left≤nums[i]≤right，令 last1=i；
否则如果 nums[i]>right，令 last2=i, last1=−1。

然后将 last1−last2累加到答案中即可。最后的总和即为题目所求。

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int res = 0, last2 = -1, last1 = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= left && nums[i] <= right) {
                last1 = i;
            } else if (nums[i] > right) {
                last2 = i;
                last1 = -1;
            }
            if (last1 != -1) {
                res += last1 - last2;
            }
        }
        return res;
    }
}

前后缀特征

有一些题目需要综合运用前后缀特征进行求解。

题目：🟩 2908. 元素和最小的山形三元组 I - 力扣（LeetCode）

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个山形三元组：

i < j < k
nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中元素和最小的山形三元组，并返回其元素和。如果不存在满足条件的三元组，返回 -1 。

除了暴力方法外，还有什么别的方法使时间复杂度将为 $O(n)$ ？

思路：枚举中间的数 nums[j]，找到 nums[j] 左边最小的值和右边最小的值，然后检查这三个数是否符合要求，再更新答案。

定义 preMin[i] 表示从 nums[0] 到 nums[i] 的最小值，定义 sufMin[i] 表示 nums[i] 到 nums[n-1] 的最小值。我们可以在 $O(n)$ 的时间内完成计算。

public int minimumSum(int[] nums) {
	int n = nums.length;

	// 计算 preMin
	int[] preMin = new int[n]; // 前缀
	preMin[0] = nums[0];
	for (int i = 1; i < n-1; i++) {
		preMin[i] = Math.min(preMin[i - 1], nums[i]); // 这其实是一种动态规划思想
	}

	// 计算 sufMin
	int[] sufMin = new int[n]; // 后缀最小值
	sufMin[n - 1] = nums[n - 1];
	for (int i = n - 2; i > 1; i--) {
		sufMin[i] = Math.min(sufMin[i + 1], nums[i]); 
	}

	// 计算最终答案
	int res = Integer.MAX_VALUE;
	for(int i=1;i<n-1;i++){
		if(preMin[i-1]<nums[i] && nums[i]>sufMin[i+1]){
			res = Math.min(res,preMin[i-1]+nums[i]+sufMin[i+1]);
		}
	}
	return res == Integer.MAX_VALUE? -1 : res;
}