fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7. 	public static void main (String[] args) throws java.lang.Exception
  8. 	{
  9. 		Scanner sc = new Scanner(System.in);
  10. 		int n = sc.nextInt();
  11. 		int[] arr = new int[n];
  12.  
  13. 		for(int i =0;i<n;i++){
  14. 			arr[i] = sc.nextInt();
  15. 		}
  16. 		int[] prefixSum = new int[n];
  17. 		prefixSum[0] = arr[0];
  18.  
  19. 		for(int i=1;i<n;i++){
  20. 		prefixSum[i] = prefixSum[i-1] + arr[i];
  21. 		}
  22.  
  23. 		int k = sc.nextInt();
  24. 		HashMap<Integer,Integer> firstOccurrence = new HashMap<>();
  25. 		HashMap<Integer,Integer> lastOccurrence = new HashMap<>();
  26. 		int minLen = Integer.MAX_VALUE, maxLen = Integer.MIN_VALUE;
  27.  
  28. 		firstOccurrence.put(0,-1);
  29. 		lastOccurrence.put(0,-1);
  30.  
  31. 		for(int j =0;j<n;j++){
  32. 		int rem = prefixSum[j] - k;
  33. 		if(firstOccurrence.containsKey(rem)){
  34. 		maxLen = Math.max(maxLen,j-firstOccurrence.get(rem));
  35. 		}
  36. 		if(lastOccurrence.containsKey(rem)){
  37. 		minLen = Math.min(minLen,j-lastOccurrence.get(rem));
  38. 		}
  39.  
  40. 		lastOccurrence.put(prefixSum[j],j);
  41. 		if(!firstOccurrence.containsKey(prefixSum[j])){
  42. 			firstOccurrence.put(prefixSum[j],j);
  43. 		}
  44. 		}
  45. 		System.out.println(minLen + " " + maxLen);
  46. }
  47. }
Success #stdin #stdout 0.18s 60696KB
comments (?)
stdin
copy 
8
0 0 1 1 0 1 2 0
2
stdout
copy 
1 5
https://ideone.com/oymH7d
language:
Java (HotSpot 12)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!