package question;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question560 {
 public int subarraySum2(int[] nums, int k) {
 Map<Integer, Integer> map = new HashMap<>();
 int res = 0;
 int sum = 0;
 map.put(0, 1);
 for (int num : nums) {
 sum += num;
 res += map.getOrDefault(sum - k, 0);
 map.put(sum, map.getOrDefault(sum, 0) + 1);
 }
 return res;
 }

 public int subarraySum(int[] nums, int k) {
 Map<Integer, Integer> map = new HashMap<>();
 int[] arr = new int[nums.length + 1];
 for (int i = 0; i < arr.length; i++) {
 if (i > 0) arr[i] = arr[i - 1] + nums[i - 1];
 map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
 }
 int res = 0;
 for (int i = 0; i < arr.length; i++) {
 Integer x = map.get(arr[i] + k);
 if (x != null) {
 if (k == 0) res += x - 1;
 else res += x;
 }
 Integer y = map.get(arr[i]);
 if (y != null) map.put(arr[i], y - 1);
 }
 return res;
 }
}

// 0 -1 -2 -1