fork download
  1. import java.util.*;
  2.  
  3. class Solution {
  4.  
  5. public int countLongestSubarraysSumK(int[] arr, int k) {
  6. Map<Integer, Integer> first = new HashMap<>();
  7. int sum = 0;
  8. int maxLen = 0;
  9. int count = 0;
  10.  
  11. first.put(0, -1);
  12.  
  13. for (int i = 0; i < arr.length; i++) {
  14. sum += arr[i];
  15.  
  16. if (first.containsKey(sum - k)) {
  17. int leftIndex = first.get(sum - k);
  18. int len = i - leftIndex;
  19.  
  20. if (len > maxLen) {
  21. maxLen = len;
  22. count = 1;
  23. } else if (len == maxLen) {
  24. count++;
  25. }
  26. }
  27.  
  28. if (!first.containsKey(sum)) {
  29. first.put(sum, i);
  30. }
  31. }
  32.  
  33. return count;
  34. }
  35. }
  36.  
  37. public class Main {
  38. public static void main(String[] args) {
  39. Scanner sc = new Scanner(System.in);
  40.  
  41. // Example input:
  42. // 6
  43. // 1 2 -1 2 -1 2
  44. // 2
  45.  
  46. int n = sc.nextInt();
  47. int[] arr = new int[n];
  48. for (int i = 0; i < n; i++)
  49. arr[i] = sc.nextInt();
  50.  
  51. int k = sc.nextInt();
  52.  
  53. Solution obj = new Solution();
  54. int ans = obj.countLongestSubarraysSumK(arr, k);
  55.  
  56. System.out.println(ans);
  57. }
  58. }
  59.  
  60.  
  61.  
  62.  
Success #stdin #stdout 0.12s 54568KB
stdin
6
1 2 -1 2 -1 2
2
stdout
2