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

[编程题]未排序正数数组中累加和为给定值的最长子数组的长度

热度指数：7159 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度

例如，arr = [1, 2, 1, 1, 1], k = 3

累加和为3的最长子数组为[1, 1, 1]，所以结果返回3

[要求]

时间复杂度为

，空间复杂度为

输入描述:

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

输出描述:

输出一个整数表示答案

示例1

输入

5 3
1 2 1 1 1

输出

备注:

算法知识视频讲解

Java

寄居的过客

import java.io.*;
import java.util.LinkedList;
import java.util.Deque;
public class Main{
public static void main(String[] args) throws IOException{
// Deque<Integer> dq = new LinkedList<>();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int l = Integer.valueOf(s[0]);
int target = Integer.valueOf(s[1]);
s = reader.readLine().split(" ");

int[] arr = new int[l];
for(int i = 0;i< l;i++){
arr[i] = Integer.valueOf(s[i]);
}
int sum=arr[0],length=0,max=0;
int left=0,right=0;
for(int i = 1;i<l;i++){
right++;
sum += arr[i];
if(sum>target){
while(sum>target){
sum-=arr[left];
left++;
}

}

//因为减去第一个可能造成出现刚好等于target的情况所以直接把判断 sum==target 放在下面避免多次判断

if(sum==target){
length = right-left+1;
max = Math.max(length,max);
sum -= arr[left];
left++;
}

}
System.out.println(max);
}

}

发表于 2022-08-11 11:13:40 回复(0)

Java

pein531

滑动窗口求解，抠边界还挺烦的，总有些诡异的错误

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(params[i]);
        int left = 0, right = 0, sum = 0, maxLen = 1;
        while(right < n){
            sum += arr[right];
            if(sum < k){
                right ++;
            }else if(sum > k){
                while(left < right && sum > k){
                    sum -= arr[left];
                    left ++;
                }
                if(sum == k) maxLen = Math.max(maxLen, right - left + 1);
                right ++;
            }else{
                maxLen = Math.max(maxLen, right - left + 1);
                sum -= arr[left];
                left ++;
                right ++;
            }
        }
        System.out.println(maxLen);
    }
}

发表于 2021-12-02 21:20:18 回复(0)

Java

眼睛想旅行121

import java.util.Scanner;

public class Main{
    public static int getMaxLength(int[] arr,int k){
        if(arr==null||arr.length==0||k<=0){
            return 0;
        }
        int left=0;
        int right=0;
        int sum=arr[0];
        int len=0;
        while (right<arr.length){
            if(sum==k){
                len=Math.max(len,right-left+1);
                sum-=arr[left++];
            }else if(sum<k){
                right++;
                if(right==arr.length){
                    break;
                }
                sum+=arr[right];
            }else{
                sum-=arr[left++];
            }
        }
        return len;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(getMaxLength(arr,k));
    }
}

发表于 2021-03-15 13:42:48 回复(0)

Java

小星教授

import java.util.*;

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=0,maxLen = Integer.MIN_VALUE;
        while(start<n && end<n){
            while(end<n){
                sum += arr[end++];
                if(sum==k){
                    maxLen = Math.max(maxLen,end-start);
                }else if(sum > k){
                    break;
                }
            }
            
            while(start < n){
                sum -= arr[start++];
                if(sum==k){
                    maxLen = Math.max(maxLen,end-start);
                }else if(sum < k){
                    break;
                }
            }
            
        }
        System.out.print(maxLen);
		
	}
}

发表于 2019-10-24 12:14:57 回复(0)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int left = 0;
        int right = 0;
        int sum = arr[left];
        int len = 0;

        while (right < n) {
            if (sum == k) {
                len = Math.max(right - left + 1, len);
                sum -= arr[left++];
            } else if (sum > k) {
                sum -= arr[left++];
            } else {
                right++;
                if (right == n) {
                    break;
                }
                sum += arr[right];
            }
        }

        System.out.println(len);
    }
}

发表于 2019-10-10 17:12:42 回复(0)