题目

image.png

思路

  • 思路一：暴力遍历每种可能性，以不同i为起点，计算它们的前缀和，再和目标值比较

  • 思路二：思路一的缺点在于，每次以不同i为起点时，都要重新计算不同的起点前缀和，如何优化计算前缀的过程，此时可以使用O(1)速度的HashMap来处理，我们知道pre[i] - pre[j] = k时，就满足一个，将其转换pre[j] = pre[i] - k ，将问题转换为求i前面的前缀和中满足值为pre[j]的条件，其中i > j，用HashMap记录以i结尾的不同前缀和，记录满足条件的个数即可

    代码

    1.   //1.暴力遍历每种可能性
    2.   public int subarraySum(int[] nums, int k) {
    3.       int count = 0;
    4.       for (int i = 0; i < nums.length; i++) {
    5.           int sum = 0;
    6.           for (int j = i; j < nums.length; j++) {
    7.               sum += nums[j];
    8.               if (sum == k) count++;
    9.           }
    10.       }
    11.       return count;
    12.   }
    14.   //2.使用前缀和+HashMap，优化计算过程
    15.   public int subarraySum(int[] nums, int k) {
    16.       int count = 0, sum = 0;
    17.       HashMap<Integer, Integer> map = new HashMap<>();
    18.       //值刚好为k时就会用到这个
    19.       map.put(0, 1);
    20.       for (int num : nums) {
    21.           sum += num;
    22.           if (map.containsKey(sum - k)) {
    23.               count += map.get(sum - k);
    24.           }
    25.           map.put(sum, map.getOrDefault(sum, 0) + 1);
    26.       }
    27.       return count;
    28.   }

    和为k的子数组