[程序员代码面试指南]数组和矩阵问题-未排序正数数组中累加和为给定值的最长子数组长度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[程序员代码面试指南]数组和矩阵问题-未排序正数数组中累加和为给定值的最长子数组长度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含671字，纯文字阅读大概需要1分钟。

内容图文

题目描述

给定无序数组，每个值均为正数，再给定整数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;
    }

内容总结

以上是互联网集市为您收集整理的[程序员代码面试指南]数组和矩阵问题-未排序正数数组中累加和为给定值的最长子数组长度全部内容，希望文章能够帮你解决[程序员代码面试指南]数组和矩阵问题-未排序正数数组中累加和为给定值的最长子数组长度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---