未排序正数数组中累加和为给定值的最长子数组长度

题目

问题: 给定一个数组 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表示最长子数组长度。

分三种情况判断,代码略:

  1. sum == k, 更新len, sum = sum-arr[left], left++
  2. sum < k, sum = sum + arr[right],right++, 同时要注意边界
  3. sum > k, sum = sum - arr[left], left++
Share