Java教程

算法-08未排序正数数组中累加和为给定值的最长连续子数组的长度

本文主要是介绍算法-08未排序正数数组中累加和为给定值的最长连续子数组的长度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

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

输入描述：

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

输出描述：

输出一个整数表示答案

示例1

输入：
5 3
1 2 1 1 1

输出：
3

思路

双指针法，计算start和end指针之间的数字和； 如果大于k，则sum减去arr[start]，并start++； 如果小于k ，先end++，再sum加上arr[end]； 如果等于k，则计算长度，sum减去arr[start]并start++； 
import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        
        int start=0,end=0,sum=arr[start],maxLen=Integer.MIN_VALUE;
            while(end<n){
                if(sum==k){
                    maxLen = Math.max(end - start + 1,maxLen);
                    sum -= arr[start++];
                } else if(sum >k){
                    sum -= arr[start++];
                } else {
                    end++;
                    if(end == n){
                        break;
                    }
                    sum += arr[end];
                }
            }
      System.out.println(maxLen);
    }
}

 

这篇关于算法-08未排序正数数组中累加和为给定值的最长连续子数组的长度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航