一维前缀和（子数组相关问题）

和等于k的最长子数组长度

思路：前缀和+哈希表。哈希表存的是key是前缀和，value是出现的位置。但这个位置必须是最早出现的，而且必须预先插入一条 0 ,-1表示0一开始就是。
然后，依次遍历数组计算前缀和，用当前的前缀和减去k的值去哈希表里面查找，当前位置减去对应的位置就是以当前位置结尾的最长子数组长度。遍历求最大即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   public static int compute() {
	map.clear();
	// 重要 : 0这个前缀和，一个数字也没有的时候，就存在了
	map.put(0, -1);
	int ans = 0;
	for (int i = 0, sum = 0; i < n; i++) {
		sum += arr[i];
		if (map.containsKey(sum - aim)) {
			ans = Math.max(ans, i - map.get(sum - aim));
		}
		if (!map.containsKey(sum)) {
			map.put(sum, i);
		}
	}
	return ans;
}

找正负数相等的最长子数组

思路： 构造前缀和，但是前缀和记录正负数数量的差值。正数为1，负数为-1，0为0.然后每到一个位置靠哈希表查询跟自己前缀和相同的位置，然后求长度，即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int compute(){
        map.put(0,-1);
        int cnt = 0;
        int ans = 0;
        for(int i =0;i<n;i++){
            cnt+= arr[i] == 0 ? 0 : arr[i]<0 ? -1 : 1;
            if(map.containsKey(cnt)){
              ans = Math.max(ans,i-map.get(cnt));
            }
            if(!map.containsKey(cnt)){
                map.put(cnt,i);
            }
        }
        return ans;
    }

表现良好的最长时间段 链接： https://leetcode.cn/problems/longest-well-performing-interval/

思路：还是前缀和+哈希表。超过时长+1，小于时长-1。如果遇到前缀和为正数说明从一开始就是满足的，返回i+1.如果为负数或者0，那么就找前缀和-1的位置（拉格朗日中值定理）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   public static int longestWPI(int[] hours) {
	// 某个前缀和，最早出现的位置
	HashMap<Integer, Integer> map = new HashMap<>();
	// 0这个前缀和，最早出现在-1，一个数也没有的时候
	map.put(0, -1);
	int ans = 0; 
	for (int i = 0, sum = 0; i < hours.length; i++) {
		sum += hours[i] > 8 ? 1 : -1;
		if (sum > 0) {
			ans = i + 1;
		} else {
			// sum <= 0
			if (map.containsKey(sum - 1)) {
				ans = Math.max(ans, i - map.get(sum - 1));
			}
		}
		if (!map.containsKey(sum)) {
			map.put(sum, i);
		}
	}
	return ans;
}

移除最少子数组长度使数组和可以被p整除

思路：以余数为前缀和，求出整个数组和的余数mod。然后在遍历过程中遇到当前余数curMod，我们就需要找到之前最后一个余数为 (curMod + p - mod)%p 的位置，然后求出长度。就是需要在当前位置移除的子数组的长度。需要最后判断长度是等于数组长度的时候，返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
   public static int minSubarray(int[] nums, int p) {
	// 整体余数
	int mod = 0;
	for (int num : nums) {
		mod = (mod + num) % p;
	}
	if (mod == 0) {
		return 0;
	}
	// key : 前缀和%p的余数
	// value : 最晚出现的位置
	HashMap<Integer, Integer> map = new HashMap<>();
	map.put(0, -1);
	int ans = Integer.MAX_VALUE;
	for (int i = 0, cur = 0, find; i < nums.length; i++) {
		// 0...i这部分的余数
		cur = (cur + nums[i]) % p;
		find = cur >= mod ? (cur - mod) : (cur + p - mod);
		// find = (cur + p - mod) % p;
		if (map.containsKey(find)) {
			ans = Math.min(ans, i - map.get(find));
		}
		map.put(cur, i);
	}
	return ans == nums.length ? -1 : ans;
}

一维差分

解释：现在要进行如下操作：

  1. 给定一个数组，我要在给定区间加上一个同样的数。循环多次
  2. 加完之后返回给我每个位置上的值。

一维差分：

  1. 区间如果为l,r 要加上a,那么我在arr[l]+a,arr[r+1]-a.
  2. 之后对这个数组求前缀和，就是结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// bookings
// [1,5,6]
// [2,9,3]
// ...
public static int[] corpFlightBookings(int[][] bookings, int n) {
	int[] cnt = new int[n + 2];
	// 设置差分数组，每一个操作对应两个设置
	for (int[] book : bookings) {
		cnt[book[0]] += book[2];
		cnt[book[1] + 1] -= book[2];
	}
	// 加工前缀和
	for (int i = 1; i < cnt.length; i++) {
		cnt[i] += cnt[i - 1];
	}
	int[] ans = new int[n];
	for (int i = 0; i < n; i++) {
		ans[i] = cnt[i + 1];
	}
	return ans;
}

等差差分

解释： 跟一维差分类似，但是我要从l到r 依次加上一个等差数列，而不是一个数。

结论： 假设这个等差数列 首项为 s , 公差为 d, 末项为 e。那对arr[l]+=s,arr[l+1]+=d-s,arr[r+1]-=d+e,arr[r+2]+=e; 然后进行两次前缀和即可。

二维前缀和

公式： sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]
计算从（a,b）到 （c,d）的子矩阵的和 : sum[c][d] - sum[a-1][d] - sum[c][b-1] + sum[a-1][b-1]

最大以1为边界的正方形

描述：给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

核心思路：构造出二维前缀和，依次枚举以（i,j）为左上角的正方形是否合法。假设以(c,d)为右下角。这个正方形的和减去以(i+1,j+1),(c-1,d-1)为对角的正方形和的值应该等于他的（边长-1） * 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static int largest1BorderedSquare(int[][] g) {
	int n = g.length;
	int m = g[0].length;
	build(n, m, g);
	if (sum(g, 0, 0, n - 1, m - 1) == 0) {
		return 0;
	}
	// 找到的最大合法正方形的边长
	int ans = 1;
	for (int a = 0; a < n; a++) {
		for (int b = 0; b < m; b++) {
			// (a,b)所有左上角点
			//     (c,d)更大边长的右下角点，k是当前尝试的边长
			for (int c = a + ans, d = b + ans, k = ans + 1; c < n && d < m; c++, d++, k++) {
				if (sum(g, a, b, c, d) - sum(g, a + 1, b + 1, c - 1, d - 1) == (k - 1) << 2) {
					ans = k;
				}
			}
		}
	}
	return ans * ans;
}

// g : 原始二维数组
// 把g变成原始二维数组的前缀和数组sum，复用自己
// 不能补0行，0列，都是0
public static void build(int n, int m, int[][] g) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			g[i][j] += get(g, i, j - 1) + get(g, i - 1, j) - get(g, i - 1, j - 1);
		}
	}
}

public static int sum(int[][] g, int a, int b, int c, int d) {
	return a > c ? 0 : (g[c][d] - get(g, c, b - 1) - get(g, a - 1, d) + get(g, a - 1, b - 1));
}

public static int get(int[][] g, int i, int j) {
	return (i < 0 || j < 0) ? 0 : g[i][j];
}

二维差分

跟一维差分差不多这里直接给公式

1
2
3
4
5
6
7
// 二维差分
	public static void add(int a, int b, int c, int d, int k) {
		diff[a][b] += k;
		diff[c + 1][b] -= k;
		diff[a][d + 1] -= k;
		diff[c + 1][d + 1] += k;
	}