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.         int count = 0;
  43.         int windowSum = 0;
  44.  
  45.         for (int j = 0; j < targetLength; j++) {
  46.             windowSum += arr[j];
  47.         }
  48.  
  49.         if (windowSum == k) {
  50.             count++;
  51.         }
  52.  
  53.         for (int j = targetLength; j < n; j++) {
  54.             windowSum += arr[j] - arr[j - targetLength];
  55.             if (windowSum == k) {
  56.                 count++;
  57.             }
  58.         }
  59.  
  60.         return count;
  61.     }
  62.  
  63.     public static void main(String[] args) {
  64.         int n = 6;
  65.         int k = 5;
  66.         int[] arr = {1, 2, 3, 4, 2, 5};
  67.  
  68.         Pair<Integer, Integer> sizes = findSubarraySizes(n, k, arr);
  69.         int maxLength = sizes.getKey();
  70.         int minLength = sizes.getValue();
  71.  
  72.         int maxCount = countSubarraysWithLength(n, k, arr, maxLength);
  73.         int minCount = countSubarraysWithLength(n, k, arr, minLength);
  74.  
  75.         System.out.println("Max Length: " + maxLength + " Count: " + maxCount);
  76.         System.out.println("Min Length: " + minLength + " Count: " + minCount);
  77.     }
  78. }
  79.  
  80. class Pair<K, V> {
  81.     private K key;
  82.     private V value;
  83.  
  84.     public Pair(K key, V value) {
  85.         this.key = key;
  86.         this.value = value;
  87.     }
  88.  
  89.     public K getKey() {
  90.         return key;
  91.     }
  92.  
  93.     public V getValue() {
  94.         return value;
  95.     }
  96. }
Success #stdin #stdout 0.15s 57236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max Length: 2 Count: 1
Min Length: 1 Count: 1
https://ideone.com/b9Cpl9
language:
Java (HotSpot 12)
created:
13 days 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!