LCR.P10[和为k的子数组]

方法一：暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int subarraySum(int[] nums, int k) {
        int ans = 0, n = nums.length;
        for (int left = 0; left < n; ++left) {
            int sum = 0;
            for (int right = left; right >= 0; --right) {
                sum += nums[right];
                if (sum == k) ++ans;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

方法二：前缀和+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int subarraySum(int[] nums, int k) {
        int ans = 0, preSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num : nums) {
            preSum += num;
            if (map.containsKey(preSum - k)) ans += map.get(preSum - k);
            map.merge(preSum, 1, Integer::sum);
            // map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$