题目
问题: 给定一个数组 arr,该数组无序,但每个值均为正数,再给定一个正数 k。求 arr 的所有子数组中所有元素相加和为 k 的最长子数组长度。 例如,arr=[1,2,1,1,1],k=3。 累加和为 3 的最长子数组为[1,1,1],所以结果返回 3。
要求: 时间复杂度 O(N),额外空间复杂度 O(1)
思路
设置两个变量left和right,代表arr[left…right]。sum表示arr[left..right]的和,len表示最长子数组长度。
分三种情况判断,代码略:
- sum == k, 更新len, sum = sum-arr[left], left++
- sum < k, sum = sum + arr[right],right++, 同时要注意边界
- sum > k, sum = sum - arr[left], left++