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
  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 + 1 - 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 + 1); // Store the latest index of the prefix sum
  49. }
  50.  
  51. // Output the count of special subarrays
  52. System.out.println(count == 0 ? 0 : count);
  53. }
  54. }
  55.  
Success #stdin #stdout 0.11s 56464KB
stdin
5 
1 2 3 4 5
5
stdout
1