题解 | #牛牛的连续子数组#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        int count = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            // 更新累加值 当前前缀和
            sum += nums[i];
            // 如果存在sum-k，那么表明子数组和存在k值 sum-k代表一个preSum,preSum = sum-k 前缀和问题 当前前缀和 - 前面前缀和 = k  sum-preSum = k = sum - (sum - k) = k
            if (hashMap.containsKey(sum - k)) {
                count += hashMap.get(sum - k);
            }
            // 更新当前前缀和 以及出现的次数
            hashMap.put(sum, hashMap.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

本题知识点分析：

1.哈希表

2.前缀和

3.动态规划

4.数组遍历

5.数学模拟

本题解题思路分析：

1.利用前缀和+哈希表在O(n)的时间复杂度下完成

2.如果是暴力需要O(n2)

3.主要思路： 找到当前前缀和 和 前面前缀和 相减 = k ，而我们要找的是preSum,前面的前缀和，因为当前前缀和一行语句就可以搞定，Sum += nums[i];

4.如果存在preSum, preSum = sum- k 也就是Sum - preSum = Sum - (Sum- k) = k, preSum[i] - preSum[j] = k

5.每次去更新当前前缀和以及出现的次数，次数就是迭代的前缀和的个数

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~