leetcode 560. 和为 K 的子数组(优质解法)

发布时间:2023年12月19日

代码:

class Solution {
    public int subarraySum(int[] nums, int k) {
        int length=nums.length;
        // key 表示前缀和,value 表示个数
        HashMap<Integer,Integer> hashMap =new HashMap<Integer,Integer>();
        //默认有一个前缀和为 0 的数据,解决下标前缀和直接为 0 的特殊情况
        hashMap.put(0,1);

        int last=0; //前一个下标的前缀和
        int now=0;  //当前下标的前缀和
        int count=0;    //记录符合条件的子数组个数
        for(int i=0;i<length;i++){
            now=last+nums[i];
            int find=now-k; //计算要在哈希表中查找的前缀和
            count+=hashMap.getOrDefault(find,0);
            //将当前下标的前缀和添加到哈希表中
            hashMap.put(now,hashMap.getOrDefault(now,0)+1);
            last=now;
        }

        return count;

    }
}

题解:

? ? ? ? 本题的题意很清晰,需要统计出该数组中和为?k?的子数组的个数?

? ? ? ? 要注意题目给出的数据范围是?-1000 <= nums[i] <= 1000,所以数组中存在小于等于 0 的数据

? ? ? ? 先来思考一下本题的暴力解法,我们将所有的子数组遍历出来,统计出其中和为?k?的子数组的个数?即可,时间复杂度为 O(n^2),这是一个很大的时间复杂度,所以我们需要进行优化

? ? ? ? 本题可以用前缀和的方式来进行优化,定义一个前缀和数组 sum,sum[ i ] 代表从 0 ~ i 的数据总和,为了便于理解,我画了如下的图:

? ? ? ? 如上图,我们要统一以下标 i 为尾的符合条件的子数组个数,就需要在 0~ i -1 中找到下标 j ,使 j 到 i 之间数据和为 k,即我们要 0~ i -1 找到 j 下标使 sum[ j-1 ] = sum [ i ] - k ,找到多少个符合条件的 j 下标就代表以下标 i 为尾的符合条件的子数组个数有多少个,更简单来说就是,在 0~ i -1 中有多少个下标的前缀和 =?sum [ i ] - k ,就代表以下标 i 为尾的符合条件的子数组个数有多少个

? ? ? ? 我们可以将已经获取到的前缀和记录到哈希表中,前缀和为 key ,个数为 value,记录在 i 下标之前,各个前缀和对应的个数

? ? ? ? 以 nums = 1,2,3? k = 3 为例,i 一开始指向 0 下标,前缀和 sum[ 0 ] = 1,我们要查找的前缀和是? sum [ 0?] - k = 1 - 3 = -2,在哈希表中没有 -2 这个前缀和对应的数目,所以没有符合条件的子数组,i 向下遍历,将当前的前缀和记录到哈希表中

1????????2????????3????????????????? ? ? ? 哈希:

????????????????????????????????????????????????????????key = 1,value =1

i

????????前缀和 sum[ 1?] = 3,我们要查找的前缀和是? sum [ 1?] - k = 3 - 3 = 0,在哈希表中没有 0?这个前缀和对应的数目,但实际上现在 0~i 之间的子数组已经是满足要求的了,所以我们这里没有考虑到? sum [ i ] - k = 0 的特殊情况,所以一开始创建哈希表时就应该添加 key = 0,value =1(前缀和为 0 的下标有一个) 这个数据

? ? ? ? 此时在哈希表中就获取到了0?这个前缀和对应的数目 1 ,我们便得到以 1 下标为尾的符合条件的子数组个数为 1,将其记录到 count 中,将当前的前缀和记录到哈希表中

1????????2????????3? ? ? ? ????????????????哈希:

? ? ? ? ? i? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????key = 0,value =1

??????????????????????????????????????????????????????key = 1,value =1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????key = 3,value =1

? ? ? ? i 继续向下遍历,??前缀和 sum[ 2?] = 6,我们要查找的前缀和是? sum [ 2?] - k = 6?- 3 = 3,在哈希表中前缀和为 3 的下标有 1 个,所以便得到以 2 下标为尾的符合条件的子数组个数为 1,将其记录到 count 中,将当前的前缀和记录到哈希表中

1????????2????????3???????????????????????? ? ? ? 哈希:

? ? ? ? ? ? ? ? ? ? i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??key = 0,value =1

???????????????????????????????????????????????????????key = 1,value =1

???????????????????????????????????????????????????????key = 3,value =1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?key = 6,value =1

? ? ? ? 而要获取当前 i 下标的前缀和很容易,我们在获取 i 下标的前缀和就已经知道 i - 1 下标的前缀和了,所以 sum[ i ] = sum[ i-1 ] + nums[ i ] ,提前设置好 0 下标之前前缀和为 0 即可

? ? ? ? ??

文章来源:https://blog.csdn.net/q322359/article/details/135062178
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。