fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		int[] arr = {1, 2, -1, 1, 1};
  13. 		int k = 3;
  14.  
  15. 		Map<Integer, Integer> prefixIndex = new HashMap<>();
  16. 		int sum = 0, minLen = Integer.MAX_VALUE;
  17.  
  18. 		prefixIndex.put(0, -1); // for subarrays starting at index 0
  19.  
  20. 		for (int i = 0; i < arr.length; i++) {
  21. 			sum += arr[i];
  22.  
  23. 			if (prefixIndex.containsKey(sum - k)) {
  24. 				minLen = Math.min(minLen, i - prefixIndex.get(sum - k));
  25. 			}
  26.  
  27. 			// always update for shortest
  28. 			prefixIndex.put(sum, i);
  29. 		}
  30.  
  31. 		if (minLen == Integer.MAX_VALUE) {
  32. 			System.out.println("No subarray with sum = " + k);
  33. 		} else {
  34. 			System.out.println("Shortest subarray length with sum = " + k + " is: " + minLen);
  35. 		}
  36. 	}
  37. }
  38.  
Success #stdin #stdout 0.13s 57436KB
comments (?)
stdin 
Standard input is empty
stdout 
Shortest subarray length with sum = 3 is: 2
https://ideone.com/NIWy1O
language:
Java (HotSpot 12)
created:
1 day 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!