【Leetcode】560.和为K的子数组

560.和为K的子数组

题目

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

方法

一种暴力方法为每次固定一个左边界，在其右边不断尝试可能的右边界，统计有多少个由这样的左右边界构成的子数组使得其中的元素和为K。这种方法时间复杂度为O(N^2)

改进解法：

  • 先遍历一次数组，计算数组中每一个元素对应的前缀和（即在数组中该元素以及它前面的所有元素的和为多少），构建前缀和数组。
  • 为了避免二次遍历，我们构建一个哈希表，其key为前缀和，value为该前缀和出现的次数。
  • 这种方法的核心思想是：要找到有多少符合preSum[i] - preSum[j] = K的情况。i为子数组右边界，j为子数组左边界。也就是说我们在遍历到位置i时，想知道在之前有多少个位置j，符合preSum[j] = preSum[i] - K。即前缀和preSum[j]出现了多少次，而这恰好可以直接从哈希表中得到。
  • 于是我们相当于用了O(N)的空间复杂度，使算法的时间复杂度降为O(N)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] preSum = new int[nums.length + 1];
        int res = 0;
        preSum[0] = 0;
        map.put(0,1);
        for(int i = 1; i <= nums.length; i++){
            preSum[i] = preSum[i - 1] + nums[i - 1];
            res += map.containsKey(preSum[i] - k) ? map.get(preSum[i] - k) : 0;
            if(!map.containsKey(preSum[i]))
                map.put(preSum[i], 1);
            else
                map.put(preSum[i], map.get(preSum[i]) + 1);
        }
        return res;
    }