fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static Pair<Integer, Integer> findSubarraySizes(int n, int k, int[] arr) {
  6.         Map<Integer, Integer> mp = new HashMap<>();
  7.         Map<Integer, Integer> mp2 = new HashMap<>();
  8.         mp.put(0, 0);
  9.         int pSum = 0;
  10.         int maxLength = 0;
  11.         int minLength = Integer.MAX_VALUE;
  12.  
  13.         for (int j = 1; j <= n; j++) {
  14.             pSum += arr[j - 1];
  15.             int x = pSum - k;
  16.  
  17.             if (mp.containsKey(x)) {
  18.                 int i = mp.get(x) + 1;
  19.                 int curLength = j - i + 1;
  20.                 if (curLength > maxLength) {
  21.                     maxLength = curLength;
  22.                 }
  23.             }
  24.  
  25.             if (mp2.containsKey(x)) {
  26.                 int i = mp2.get(x) + 1;
  27.                 int curLength = j - i + 1;
  28.                 if (curLength < minLength) {
  29.                     minLength = curLength;
  30.                 }
  31.             }
  32.  
  33.             mp.putIfAbsent(pSum, j);
  34.             mp2.put(pSum, j);
  35.         }
  36.  
  37.         return new Pair<>(maxLength, minLength);
  38.     }
  39.  
  40.     public static int countSubarraysWithLength(int n, int k, int[] arr, int targetLength) {
  41.         if (targetLength == 0) return 0;
  42.  
  43.         if (targetLength == Integer.MAX_VALUE) return 0;
  44.         int count = 0;
  45.         int windowSum = 0;
  46.  
  47.         for (int j = 0; j < targetLength; j++) {
  48.             windowSum += arr[j];
  49.         }
  50.  
  51.         if (windowSum == k) {
  52.             count++;
  53.         }
  54.  
  55.         for (int j = targetLength; j < n; j++) {
  56.             windowSum += arr[j] - arr[j - targetLength];
  57.             if (windowSum == k) {
  58.                 count++;
  59.             }
  60.         }
  61.  
  62.         return count;
  63.     }
  64.  
  65.     public static void main(String[] args) {
  66.         int n = 6;
  67.         int k = 200;
  68.         int[] arr = {1, 2, 3, 4, 2, 5};
  69.  
  70.         Pair<Integer, Integer> sizes = findSubarraySizes(n, k, arr);
  71.         int maxLength = sizes.getKey();
  72.         int minLength = sizes.getValue();
  73.  
  74.         int maxCount = countSubarraysWithLength(n, k, arr, maxLength);
  75.         int minCount = countSubarraysWithLength(n, k, arr, minLength);
  76.  
  77.         System.out.println("Max Length: " + maxLength + " Count: " + maxCount);
  78.         System.out.println("Min Length: " + minLength + " Count: " + minCount);
  79.     }
  80. }
  81.  
  82. class Pair<K, V> {
  83.     private K key;
  84.     private V value;
  85.  
  86.     public Pair(K key, V value) {
  87.         this.key = key;
  88.         this.value = value;
  89.     }
  90.  
  91.     public K getKey() {
  92.         return key;
  93.     }
  94.  
  95.     public V getValue() {
  96.         return value;
  97.     }
  98. }
  99.  
Success #stdin #stdout 0.14s 55320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max Length: 0 Count: 0
Min Length: 2147483647 Count: 0
https://ideone.com/mLUNpx
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!