【LeetCode】Day108-和为 K 的子数组

题目

560. 和为 K 的子数组【中等】

题解

枚举法

实际上就是暴力计算，双重循环

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        int n=nums.length;
        int count=0;
        for(int i=0;i<n;i++){
    
            int sum=0;
            for(int j=i;j<n;j++){
    
                sum+=nums[j];
                if(sum==k)
                    count++;
            }
        }
        return count;
    }
}

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

前缀和+哈希表

这个逻辑非常的妙

首先，基于方法一，对于每一个 i ，我们都要枚举 j 来判断是否符合条件，这个过程是否可以用数据结构精简呢？
我们定义 pre[i] 为 [0…i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即$$pre[i]=pre[i-1]+nums[i]$$
那么「[j…i] 这个子数组和为 k 」这个条件我们可以转化为 $$pre[i]-pre[j-1]==k，$$再进行简单移项，得到 $$pre[j-1]==pre[i]-k$$
所以我们考虑 i 有多少个前缀和为 pre[i]−k 的 pre[j] 即可。

其次，建立哈希表mp，以 和-次数 为键值对，记录 pre[i] 出现的次数，从左往右边更新 mp 边计算答案，那么以 i 结尾的答案 mp[pre[i]−k] 即可在 O(1) 时间内得到

进一步优化，由于pre[i]只和pre[i-1]有关，因此可以不用建立pre数组，直接用变量pre来记录答案。

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        int n=nums.length;
        int pre=0,count=0;
        Map<Integer,Integer>mp=new HashMap<>();
        mp.put(0,1);//0->i前缀和数组 恰好为k的情况，做一个初始化
        for(int i=0;i<n;i++){
    
            pre+=nums[i];
            if(mp.containsKey(pre-k))
                count+=mp.get(pre-k);
            mp.put(pre,mp.getOrDefault(pre,0)+1);
        }
        return count;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$