前缀和

通常，涉及连续子数组问题的时候，我们使用前缀和来解决。

  • 我们令 P[i] = A[0] + A[1] + … + A[i]
  • 那么每个连续子数组的和 sum(i, j) = P[j] - P[i-1]（其中 0 < i < j）。

例如：

560. 和为K的子数组

1
2
3
4
5
6
7
8
9
10
11
12
public int subarraySum(int[] nums, int k) {
    int res = 0,sum = 0;
    HashMap<Integer,Integer> map = new HashMap<>();
    map.put(0,1);
    for (int n:nums) {
        sum += n;
        // sum1 - k = sum2
        if(map.containsKey(sum-k)) res += map.get(sum-k);
        map.put(sum,map.getOrDefault(sum,0)+1);
    }
    return res;
}

974. 和可被 K 整除的子数组

前缀和+同余定理 p[j]- p[i] % K = 0 等价于 p[j] % k == p[i] % K

1
2
3
4
5
6
7
8
9
10
11
12
13
public int subarraysDivByK(int[] A, int K) {
	int sum = 0, res = 0;
	Map<Integer, Integer> map = new HashMap<>();
	map.put(0, 1);
	for (int n : A) {
		sum += n;
		int curMod = (sum%K+K)%K;   // 变负为正
		int preCount = map.getOrDefault(curMod, 0);
		res += preCount;
		map.put(curMod, preCount + 1);
	}
	return res;
}

若K的数量级不高可以用数组代替map

1
2
3
4
5
6
7
8
9
10
11
public int subarraysDivByK(int[] A, int k) {
	int[] dp = new int[k];
	dp[0] = 1;
	int res=0,sum=0;
	for(int n:A){
		sum = ((sum+n)%k+k)%k;
		res += dp[sum];
		dp[sum]++;
	}
	return res;
}

类似前缀和的前缀积

  • 由于是前缀积，所以一般不像前缀和是正负波动的，而是递增的，且数量大
  • 所以不能用存储记录，而是用（滑动窗口）

例如：

713. 乘积小于K的子数组

前缀积 + 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
public int numSubarrayProductLessThanK(int[] nums, int k) {
	if(k<=1) return 0;
	int res = 0,sum = 1,l = 0;
	for (int r = 0; r <nums.length ; r++) {
		sum *= nums[r];
		while (sum >= k){
			sum /= nums[l];
			l++;
		}
		res += (r-l+1);
	}
	return res;
}