二、求子数组和为k的最大长度

题目：

给定一个数组 arr，该数组无序，但每个值均为正数，再给定一个正数 k。求 arr的所有子数组中所有元素相加和为 k 的最长子数组长度。例如，arr=[1,2,1,1,1]，k=3。累加和为 3 的最长子数组为[1,1,1]，所以结果返回 3。

【要求】

时间复杂度 O(N)，额外空间复杂度 O(1)

思路：定义两个指针left和right，初始时left和right都指向0位置。sum记录left和right之间元素之和，初始sum=0。len记录当前最长子数组长度，初始时len=0

• 当sum<k时，sum+=arr[right]，然后right往右移动
• 当sum>k时，sum-=arr[left]，然后left向右移动
• 当sum=k时，计算这时数组的长度temp=right-left。比较len与temp的长度大小。然后再计算sum+=arr[right]，right向右滑动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static int (int[] arr, int k)
{
	if (arr == null || arr.length < 1)
		return 0;
	int left = 0, right = 0;
	int sum = 0;
	int len = 0;
	while (right < arr.length)
	{
		if (sum < k)
		{
			sum += arr[right++];
		} else if (sum > k)
		{
			sum -= arr[left++];
		} else
		{
			int temp = right - left;
			len = len < temp ? temp : len;
			sum += arr[right++];
		}
	}
	return len;
}

​