fork download
  1. import java.util.*;
  2.  
  3. class Main {
  4. public static void main(String[] args) {
  5. Scanner sc = new Scanner(System.in);
  6.  
  7. // Read the size of the array
  8. int n = sc.nextInt();
  9. int[] arr = new int[n];
  10.  
  11. // Read the elements of the array
  12. for (int i = 0; i < n; i++) {
  13. arr[i] = sc.nextInt();
  14. }
  15.  
  16. // Read the target sum k
  17. int k = sc.nextInt();
  18.  
  19. // Initialize variables
  20. int currentSum = 0;
  21. int smallestLength = Integer.MAX_VALUE;
  22. int count = 0;
  23.  
  24. // Map to store the frequency of prefix sums
  25. Map<Integer, Integer> map = new HashMap<>();
  26.  
  27. // Initialize the map with the prefix sum of 0 coz what if i get k=5, and arr[0]=5
  28. map.put(0, -1);
  29.  
  30. for (int i = 0; i < n; i++) {
  31. // Update the current prefix sum
  32. currentSum += arr[i];
  33.  
  34. // Check if there exists a prefix sum that gives us the required sum k
  35. if (map.containsKey(currentSum - k)) {
  36. int length = i - map.get(currentSum - k);
  37.  
  38. // Update the smallest length and count
  39. if (length < smallestLength) {
  40. smallestLength = length;
  41. count = 1; // Reset count for new smallest length
  42. } else if (length == smallestLength) {
  43. count++; // Increment count for same smallest length
  44. }
  45. }
  46.  
  47. // Update the frequency of the current prefix sum
  48. map.put(currentSum, i); // Store the latest index of the prefix sum
  49. /*
  50.   say 1 2 3 4 5
  51.   at end 15 so now i want length (i+1(0 indexed)) - map.containskey(currsum, i+1)
  52.   jth index - i+1 where subarray sum starts but the i+1 in the map is solely coz of 0 indexing
  53.   but i didnt like how it made lengths of 1 to become 0 so i made it i itself and put the map
  54.   start at (0,-1) prefix sum of 0 is at -1 so it doesnt exist yet
  55.   */
  56. }
  57.  
  58. // Output the count of special subarrays
  59. System.out.println(count == 0 ? 0 : count);
  60. }
  61. }
  62.  
Success #stdin #stdout 0.15s 54420KB
stdin
5
5 1 2 3 4
5
stdout
1