题目描述
给定无序数组, 每个值均为正数, 再给定整数 k. 求 arr 中所有子数组中所有元素相加和为 k 的最长子数组长度. 无则输出 - 1.
例:
输入 arr=[1,2,1,1,1],k=3
输出 3
解题思路 (时间复杂度 O(N), 空间复杂度 O(1))
维护指针 l,r 表示子数组区间. 初始 l=r=0, 向右移动至 r=arr.length 结束.
维护当前子数组和 sum, 及到当前为止满足题意的最大 len. 初始 sum=arr[0],len=-1.
每次比较 sum 和 k, 根据情况选择移动 l 还是 r, 并更新 sum 和 len.
代码
- public static int longestEqualStrLen(int[] arr,int k) {
- int l=0;
- int r=0;
- int sum=arr[0];
- int len=-1;
- while(r<arr.length) {
- if(sum<k) {
- r++;
- if(r==arr.length) {
- break;
- }
- sum+=arr[r];
- }
- else if(sum>k) {
- l++;
- sum-=arr[l];
- }
- else {
- if(r-l+1>len) {
- len=r-l+1;
- }
- l++;
- sum=-arr[l];
- }
- }
- return len;
- }
[程序员代码面试指南] 数组和矩阵问题 - 未排序正数数组中累加和为给定值的最长子数组长度
来源: http://www.bubuko.com/infodetail-3051998.html