给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

    示例 1：
    输入：nums = [1,1,1], k = 2
    输出：2

    示例 2：
    输入：nums = [1,2,3], k = 3
    输出：2

    常规算法：

    1. public int subarraySum(int[] nums, int k) {
    2.     int count = 0;
    3.     // 外层循环控制子数组最大长度
    4.     for (int i = 0; i < nums.length; i++) {
    5.         int sum = 0;
    6.         // 内层循环计算是否存在子数组的和满足要求
    7.         for (int j = i; j < nums.length; j++) {
    8.             sum += nums[j];
    9.             if (sum == k) {
    10.                 count++;
    11.             }
    12.         }
    13.     }
    14.     return count;
    15. }

    子数组类型问题还可以利用前缀和的算法思想

    1. public int subarraySum(int[] nums, int k) {
    2.     // 前缀和数组
    3.     int[] sums = new int[nums.length+1];
    4.     for (int i = 0; i < nums.length; i++) {
    5.         // 这里需要注意，前缀和是从 presum[1]开始填充的
    6.         sums[i + 1] = sums[i] + nums[i];
    7.     }
    8.     // 统计 sums 中两个元素的差 等于 k 的次数
    9.     int count = 0;
    10.     for (int i = 0; i < sums.length - 1; i++) {
    11.         for (int j = i; j < sums.length - 1; j++) {
    12.             if (sums[j + 1] - sums[i] == k) {
    13.                 count++;
    14.             }
    15.         }
    16.     }
    17.     return count;
    18. }

    但是此写法和常规遍历并没有更优，返而空间复杂度上升了，但是可以利用哈希进行优化（只是不容易想到）

    可以参考 1. 两数之和
    常规双层循环：

    1. public int[] towSum(int[] nums, int target) {
    2.     for(int i = 0; i < nums.length; i++) {
    3.         for(int j = 0; j < nums.length; j++) {
    4.             if (i != j && nums[i] + nums[j] == target) {
    5.                 return new int[] {i, j};
    6.             }
    7.         }
    8.     }
    9.     return new int[]{};
    10. }

    哈希优化双层循环：

    1.  public int[] towSum(int[] nums, int target) {
    2.     Map<Integer, Integer> map = new HashMap<>();
    3.     for(int i = 0; i < nums.length; i++) {
    4.         map.put(nums[i], i);
    5.     }
    6.     for(int i = 0; i < nums.length; i++) {
    7.         int diff = target - nums[i];
    8.         if (map.containsKey(diff) && map.get(diff) != i) {
    9.             return new int[] {i, map.get(diff)};
    10.         }
    11.     }
    12.     return new int[]{};
    13. }

    哈希再优化：

    1. public int[] towSum(int[] nums, int target) {
    2.     Map<Integer, Integer> map = new HashMap<>();
    3.     for(int i = 0; i < nums.length; i++) {
    4.         int diff = target - nums[i];
    5.         if (map.containsKey(diff) && map.get(diff) != i) {
    6.             return new int[] {i, map.get(diff)};
    7.         }
    8.         map.put(nums[i], i);
    9.     }
    10.     return new int[]{};
    11. }

    前缀和的哈希优化：

    1. public int subarraySum(int[] nums, int k) {
    2.     if (nums.length == 0) {
    3.         return 0;
    4.     }
    5.     int count = 0;
    6.     HashMap<Integer,Integer> map = new HashMap<>();
    7.     // 细节，这里需要预存前缀和为 0 的情况
    8.     map.put(0, 1);
    9.     int presum = 0;
    10.     for (int x : nums) {
    11.         presum += x;
    12.         // 当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
    13.         if (map.containsKey(presum - k)) {
    14.             // 累加次数
    15.             count += map.get(presum - k);
    16.         }
    17.         // 更新
    18.         map.put(presum, map.getOrDefault(presum,0) + 1);
    19.     }
    20.     return count;
    21. }