---

题目一

给定一个正整数组成的无序数组arr，给定一个正整数值K
找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的
返回其长度

解题思路

因为该数组全为正数,因此具有单调性,可以使用滑动窗口解
窗口不断右移扩大,记录窗口最大长度
当窗口累加和sum<k 右扩
当sum==k 记录
当sum>k 左缩

代码

public static int getMaxLength(int[] arr, int K) {
	if (arr == null || arr.length == 0 || K <= 0) {
		return 0;
	}
	int left = 0;
	int right = 0;
	int sum = arr[0];
	int len = 0;
	while (right < arr.length) {
		if (sum == K) {
			len = Math.max(len, right - left + 1);
			sum -= arr[left++];
		} else if (sum < K) {
			right++;
			if (right == arr.length) {
				break;
			}
			sum += arr[right];
		} else {
			sum -= arr[left++];
		}
	}
	return len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目二

给定一个整数组成的无序数组arr，值可能正、可能负、可能0
给定一个整数值K
找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的
返回其长度

解题思路

与题目1不同的是,数组有正负0,因此失去了单调性,不能使用滑动窗口

看到子数组,我们需要往以i开头的子数组或者以i结尾的子数组这个方向思考

在这题,我们考虑以0为结尾的子数组到以结尾位置为结尾的子数组,哪个子数组最长

例如
i来到100位置,i位置的前缀和为200,需要求以i为结尾,累加和为30的最长的子数组长度
我们需要找到第一次出现前缀和为170的位置,假设为j,则子数组长度为i-j=80
我们可以使用哈希表记录第一次出现前缀和为x的位置

代码

	public static int maxLength(int[] arr, int k) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// key:前缀和
		// value : 0~value这个前缀和是最早出现key这个值的
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(0, -1); // important
		int len = 0;
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			if (map.containsKey(sum - k)) {
				len = Math.max(i - map.get(sum - k), len);
			}
			if (!map.containsKey(sum)) {
				map.put(sum, i);
			}
		}
		return len;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

问题三

给定一个整数组成的无序数组arr，值可能正、可能负、可能0
给定一个整数值K
找到arr的所有子数组里，哪个子数组的累加和<=K，并且是长度最大的
返回其长度

解题思路

我们需要使用两个辅助数组
minSum[i]:如果子数组必须以i开头,哪一个以i开头的子数组能取得最小的累加和,这个最小的累加和填到minSum[i]里
minSumEnd[i]:必须以i开头的子数组,当它取得最小累加和的时候右边界的位置
从右往左便利一遍生成两个子数组生成时从后往前填,从右往左遍历一遍,生成两个辅助数组

生成好两个辅助数组,我们可以用滑动窗口解决该题
用窗口先看必须以0开头的子数组,怎么样得到最小累加和

假设扩出的第一块是0~6位置。这一块就是零开头的情况下所取得的最小累加和,设为a,且a<=k(如果a>k则扩结束了)。如果a是小于等于K的,下面我把7开头能够取得最小累加和算做b我看看a+b是不是小于等于K的。如果还是我接着扩,看加上之后是不是小于等于K的,我一直扩到大于K的时候。

如图,我们最多可以扩到c这个位置,如果再加上d就超过k了,因此以0为开头,最长子数组长度为17
到1位置,我们需要前缀和减去nums[0]这个数,然后再看看加上d会不会超过k,如果没有超过那么加上d这个部分,如果超过了,那么就在看2位置,以此类推,如果直到16位置还没能扩大窗口,那么在17位置重开一个窗口

代码

	public static int maxLengthAwesome(int[] arr, int k) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int[] minSums = new int[arr.length];
		int[] minSumEnds = new int[arr.length];
		minSums[arr.length - 1] = arr[arr.length - 1];
		minSumEnds[arr.length - 1] = arr.length - 1;
		for (int i = arr.length - 2; i >= 0; i--) {
			if (minSums[i + 1] < 0) {
				minSums[i] = arr[i] + minSums[i + 1];
				minSumEnds[i] = minSumEnds[i + 1];
			} else {
				minSums[i] = arr[i];
				minSumEnds[i] = i;
			}
		}
		// 迟迟扩不进来那一块儿的开头位置
		int end = 0;
		int sum = 0;
		int ans = 0;
		for (int i = 0; i < arr.length; i++) {
			// while循环结束之后：
			// 1) 如果以i开头的情况下，累加和<=k的最长子数组是arr[i..end-1]，看看这个子数组长度能不能更新res；
			// 2) 如果以i开头的情况下，累加和<=k的最长子数组比arr[i..end-1]短，更新还是不更新res都不会影响最终结果；
			while (end < arr.length && sum + minSums[end] <= k) {
				sum += minSums[end];
				end = minSumEnds[end] + 1;
			}
			ans = Math.max(ans, end - i);
			if (end > i) { // 还有窗口，哪怕窗口没有数字 [i~end) [4,4)
				sum -= arr[i];
			} else { // i == end,  即将 i++, i > end, 此时窗口概念维持不住了，所以end跟着i一起走
				end = i + 1;
			}
		}
		return ans;
	}
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