子数组累加和系列问题

题目

给定一个无序数组arr，其中元素可正、可负、可0，再给定一个整数k，求arr所有的子数组中累加和为k的最长子数组长度。

思路

如果暴力的算就是遍历所有子数组，求所有和为k的长度，求出最大，时间复杂度是o(n*n)
还可以用sum表示所有以i结尾的数组的和，如果sum[i]-k=sum[j]，则说明(j,i]的区间上的和是k
那么可以用hashMap记录下所有出现的和的第一次，然后每次进行比较则可以算出
时间复杂度是O(n)

代码

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
public static int getKLen(int[] arr, int k){
	//key表示和的数值，value表示第一次出现该值的位置
	//该map只记录第一次出现的情况
	HashMap<Integer, Integer> mymap = new HashMap<Integer, Integer>();
	//因为和0的记录是所有值都不取，不会被自动加入
	//因此这里添加，表示从开头是选
	mymap.put(0, -1);
	int sum = 0;
	int len = 0;
	for (int i = 0; i < arr.length; i++) {
		//以i结尾的和
		sum += arr[i];
		//只记录第一次出现的和，因为这样才能最长
		if(!mymap.containsKey(sum)){
			mymap.put(sum, i);
		}
		//如果有sum[j]+k=sum[i]，说明(j,i]的部分和是k
		if(mymap.containsKey(sum - k)){
			int j = mymap.get(sum - k);
			//以j结尾的和和以i结尾的和，期间的长度是i-j
			len = Math.max(len, i - j);
		}
	}
	return len;
}

题目

给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。
求arr的所有子数组中所有元素相加和为k的最长子数组长度。例如，arr=[1,2,1,1,1]，k=3。
累加和为3的最长子数组为[1,1,1]，所以结果返回3。
要求：时间复杂度O(N)，额外空间复杂度O(1)。

思路

该题目遇上一题的区别就是正数
因此该题目可以用一个区间来找和是k的组合

  • left区间的左端
  • right区间的右端
  • sum该区间的和
  • len最大的长度

开始left和right都指向0，一边计算sum一边更新len

  • sum > k right右移，继续增加区间的长度
  • sum < k left右移，减少区间元素，使得和减小
  • sum == k left右移，等于之后要更新len，为了检测是否有更多和为k的子数组，要继续遍历

代码

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
public static int getMaxKLen(int[] a,int k){
	if(a.length < 0 || k <= 0 || a == null){
		return 0;
	}
	int left = 0;
	int right = 0;
	//这里sum已经设置了，后面要先改区间，再算和
	int sum = a[0];
	int len = 0;
	while(left < a.length && right < a.length) {
		if(sum < k){
			//先改区间，再算和
			right ++;
			if (right == a.length) {
				break;
			}
			sum += a[right];
		}else if(sum > k){
			//先改区间，再算和
			left++;
			sum -= a[left];
		}else{
			//sum== k
			len = Math.max(len, right - left + 1);
			left++;
			sum -= a[left];
			
		}
		
	}
	return len;
}

题目

给定一个无序数组arr，其中元素可正、可负、可0，给定一个整数 k。
求arr所有的子数组中累加和小于或等于k的最长子数组长度。
例如:arr=[3,-2,-4,0,6]，k=-2，相加和小于或等于-2的最长子数组为{3,-2,-4,0}，所以结果返回4

思路

回顾上面的题目，用一个数组记录当前位置所有和，然后一边遍历，一边算现在的和，
当遍历到i时，用x=当前和-k，找所有和中是否有x值，有就说明该位置到当前位置和是k
而本题目是所求的和小于等于k值，对于等式x=当前和-k,这里k<=aa,因此x>=和-aa,而遍历的过程是寻找数组中大于等于和-a[i]的值

对于一个序列，求最长则需要找到第一个大于等于的值
因此辅助数组改为记录当前位置和的最大值，是一个递增序列
例如[-2,4,2,0,2,1]求第一个大于等于2的位置，那么就是4的位置
因此序列改为[-2,4,4,4,4],这样对于递增序列，可以用二分降到O(log(n))
整体的复杂度为O(n*log(n))

代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public static int maxLength(int[] arr, int k) {
	// 记录当前位置出现的最大和，是一个递增数组
	int[] h = new int[arr.length + 1];
	int sum = 0;
	// 加入和是0的记录
	h[0] = sum;
	for (int i = 0; i != arr.length; i++) {
		sum += arr[i];
		h[i + 1] = Math.max(sum, h[i]);
	}
	sum = 0;
	// 结果
	int res = 0;
	// 满足区间的左边界
	int pre = 0;
	// 长度，右边界-左边界+1
	int len = 0;
	for (int i = 0; i != arr.length; i++) {
		// 当前所有的和
		sum += arr[i];
		// k+x=sum
		// 求小于等于k的区间，那么就要找到大于等于x即(sum-k)的值
		// 即求出第一个大于x的位置
		pre = getIndex(h, sum - k);
		// 可能找不到
		len = pre == -1 ? 0 : i - pre + 1;
		res = Math.max(res, len);
	}
	return res;
}
// 第一个大于x的位置R
public static int getIndex(int[] a, int x) {
	int left = 0;
	int right = a.length;
	int mid = 0;
	// 有可能出现找不到的情况
	int res = -1;
	// 区间是[0,n)
	// 分支中出现了l=mid 或者r=mid，循环条件要写成left < right，否则写成left <= right
	// 避免出现left=right-1出现死循环
	while (left < right) {
		mid = (left + right) / 2;
		// 第一个大于x的元素，没有等号
		if (a[mid] > x) {
			// 找不到的情况是x比任何数都大，因此如果存在都会进左区间
			// 右区间找不到情况下是不进入的
			// 用res来记录，如果找到不进入此，不改变值，返回-1
			res = mid;
			// 在区间[left,mid)找
			right = mid;
		} else {
			// 在区间[mid+1,right)找
			left = mid + 1;
		}
	}
	// 找不到
	return res;
}