给定一个数组arr,该数组无序,但每个值均为正数,再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度
例如,arr = [1, 2, 1, 1, 1], k = 3
累加和为3的最长子数组为[1, 1, 1],所以结果返回3
[要求]
时间复杂度为,空间复杂度为
第一行两个整数N, k。N表示数组长度,k的定义已在题目描述中给出
第二行N个整数表示数组内的数
输出一个整数表示答案
5 3 1 2 1 1 1
3
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); } }
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)); } }
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); } }
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); } }