fork(5) download
copy 
  1. import java.util.HashMap;
  2.  
  3. class SmallestWindow {
  4. 	public SmallestWindow(int[] inp, int[] query) {
  5. 		int[] best = { -1, -1, Integer.MAX_VALUE };
  6. 		HashMap<Integer, Pair> M = new HashMap<Integer, Pair>();
  7. 		for (int i = 0; i < query.length; i++)
  8. 			M.put(query[i], new Pair(-1, i));
  9. 		for (int i = 0; i < inp.length; i++) {
  10. 			Pair currPair = M.get(inp[i]);
  11. 			if (currPair == null)
  12. 				continue;
  13. 			if (currPair.P == 0) {
  14. 				currPair.I = i;
  15. 				continue;
  16. 			}
  17. 			currPair.I = M.get(query[currPair.P - 1]).I;
  18. 			if (currPair.P == query.length - 1 && currPair.I != -1
  19. 					&& i - currPair.I < best[2]) {
  20. 				best[0] = currPair.I;
  21. 				best[1] = i;
  22. 				best[2] = i - currPair.I;
  23. 			}
  24. 		}
  25. 		System.out.println("[" + best[0] + ".." + best[1] + "]");
  26. 	}
  27.  
  28. 	public static void main(String[] args) {
  29. 		int[] inputArray = new int[] { 2, 0, 2, 1, 0, 1, 0, 7 };
  30. 		int[][] queryArrays = new int[][] { { 2, 1, 7 }, { 2, 0 }, { 2, 1 } };
  31. 		for (int[] q : queryArrays)
  32. 			new SmallestWindow(inputArray, q);
  33. 	}
  34.  
  35. 	public class Pair {
  36. 		private int I, P;
  37.  
  38. 		public Pair(int I, int P) {
  39. 			this.I = I;
  40. 			this.P = P;
  41. 		}
  42. 	}
  43. }
  44.  
Success #stdin #stdout 0.05s 213312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[2..7]
[0..1]
[2..3]
https://ideone.com/5gElF
language:
Java (HotSpot 12)
created:
13 years ago
visibility:
secret

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!