fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static int[] findSubarraySizes(int n, int k, int[] arr) {
  6.         Map<Integer, Integer> firstOccurrence = new HashMap<>();
  7.         Map<Integer, Integer> lastOccurrence = new HashMap<>();
  8.         firstOccurrence.put(0, 0);
  9.  
  10.         int prefixSum = 0, maxLength = 0, minLength = Integer.MAX_VALUE;
  11.  
  12.         for (int j = 1; j <= n; j++) {
  13.             prefixSum += arr[j - 1];
  14.             int target = prefixSum - k;
  15.  
  16.             if (firstOccurrence.containsKey(target)) {
  17.                 maxLength = Math.max(maxLength, j - firstOccurrence.get(target));
  18.             }
  19.  
  20.             if (lastOccurrence.containsKey(target)) {
  21.                 minLength = Math.min(minLength, j - lastOccurrence.get(target));
  22.             }
  23.  
  24.             firstOccurrence.putIfAbsent(prefixSum, j);
  25.             lastOccurrence.put(prefixSum, j);
  26.         }
  27.  
  28.         return new int[]{maxLength, minLength};
  29.     }
  30.  
  31.     public static int countSubarraysWithLength(int n, int k, int[] arr, int length) {
  32.         if (length == 0) return 0;
  33.  
  34.         int count = 0, sum = 0;
  35.  
  36.         for (int j = 0; j < length; j++) {
  37.             sum += arr[j];
  38.         }
  39.  
  40.         if (sum == k) count++;
  41.  
  42.         for (int j = length; j < n; j++) {
  43.             sum += arr[j] - arr[j - length];
  44.             if (sum == k) count++;
  45.         }
  46.  
  47.         return count;
  48.     }
  49.  
  50.     public static void main(String[] args) {
  51.         int n = 6, k = 5;
  52.         int[] arr = {1, 2, 3, 4, 2, 5};
  53.  
  54.         int[] sizes = findSubarraySizes(n, k, arr);
  55.         int maxLength = sizes[0], minLength = sizes[1];
  56.  
  57.         int maxCount = countSubarraysWithLength(n, k, arr, maxLength);
  58.         int minCount = countSubarraysWithLength(n, k, arr, minLength);
  59.  
  60.         System.out.println("Max Length: " + maxLength + " Count: " + maxCount);
  61.         System.out.println("Min Length: " + minLength + " Count: " + minCount);
  62.     }
  63. }
  64.  
Success #stdin #stdout 0.18s 55460KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Max Length: 2 Count: 1
Min Length: 1 Count: 1
https://ideone.com/2CHgnb
language:
Java (HotSpot 12)
created:
16 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!