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

题目描述

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

输入描述:

第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出
第二行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入
5 3
1 2 1 1 1

输出
3

解题

import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        int[] arr = new int[n];
        int j = 0;
        for(String i:in.readLine().split(" ")){
            arr[j++] = Integer.parseInt(i);
        }
        System.out.println(getLength(arr,k));
        
    }
    
    static int getLength(int[] arr,int k){
        //定义len，保存子数组长度
        int len = 0;
        //定义两个窗口指针
        int left = 0,right = 0;
        //定义窗口中的元素和
        int sum = arr[right];
        while(right<arr.length){
            //如果窗口元素和小于k，表示窗口边界可以继续向右移，注意控制边界不要溢出
            if(sum < k){
                right++;
                if(right==arr.length)
                    break;
                sum += arr[right];
            }else if(sum == k){//如果sum=k，判断是否更新为更大的len
                if(len<right-left+1)
                    len = right-left+1;
                //不管len是否更新，这个时候窗口右边界没法扩展了，只能移动窗口左边界
                sum -= arr[left++];
            }else{
                //如果sum>k,同样只能从左边界缩小以形成可以继续向右探索的条件
                sum -= arr[left++];
            }
        }
        return len;
    }
    
}