剑指 Offer II 010. 和为 k 的子数组

这篇具有很好参考价值的文章主要介绍了剑指 Offer II 010. 和为 k 的子数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。

示例 1:

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1][1,1] 为两种不同的情况

示例 2:

输入:nums = [1,2,3], k = 3
输出: 2

提示:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

这个题目做出来不难,直接暴力枚举。但是利用哈希表和前缀和优化的过程我一直不是很理解,所以写下这篇文章来一点一点的研究,希望能对大家有所帮助

首先,先看最简单的暴力解法:

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

这个解法相比大家都能想的出来,就不在此深究了。
接下来看另外一种暴力解法:

利用前缀和暴力解题:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int len = nums.length;
        int[] pre = new int[len+1];

        for(int i=1;i<=len;i++){
            pre[i] = pre[i-1]+nums[i-1];
        }

        for(int i=0;i<=len;i++){
            for(int j=i+1;j<=len;j++){
                if(pre[j] - pre[i] == k) ++count;
            }
        }
        return count;
    }
}

下面讲一下思路:
剑指 Offer II 010. 和为 k 的子数组
这种做法依旧很好理解。时间复杂度依旧很高,我们要继续优化。
这种双循环会使得有个别元素遍历了很多次。这是可以优化的地方。
下面我们研究一下 pre[i] , pre[j] ,和 k 的关系
剑指 Offer II 010. 和为 k 的子数组
看到这里大家应该已经理解了,当然也可能是我描述的不够清晰导致大家没能理解(见谅)
代码如下:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int len = nums.length;
        int[] pre = new int[len+1];
        Map<Integer,Integer> map = new HashMap();
        map.put(0,1);
        for(int i=1;i<=len;i++){
            pre[i] = pre[i-1]+nums[i-1];
        }

        for(int i=1;i<=len;i++){
            if(map.containsKey(pre[i]-k)){
                count+=map.get(pre[i]-k);
            }
            map.put(pre[i], map.getOrDefault(pre[i], 0) + 1);
        }
        return count;
    }
}

这样只用一个循环就搞定了。但是还可以再优化
我们思考 pre[] 数组真的需要吗?

for(int i=1;i<=len;i++){
        if(map.containsKey(pre[i]-k)){
            count+=map.get(pre[i]-k);
        }
        map.put(pre[i], map.getOrDefault(pre[i], 0) + 1);
}

我们发现 每次循环只用了 当前的 pre[i];前面的都没用到

for(int i=1;i<=len;i++){
            pre[i] = pre[i-1]+nums[i-1];
}

for(int i=1;i<=len;i++){
        if(map.containsKey(pre[i]-k)){
            count+=map.get(pre[i]-k);
        }
        map.put(pre[i], map.getOrDefault(pre[i], 0) + 1);
}

那么上面这个循环完全可以写进下面这个循环

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int len = nums.length;
        int pre = 0;//用变量去迭代前缀和就行
        Map<Integer,Integer> map = new HashMap();
        map.put(0,1);
        
        for(int i=0;i<len;i++){//这里 i 要从 0 开始,因为操作的是 nums[i] 
            pre+=nums[i];//这一步就相当于 pre[i] ,大家可以理解一下
            if(map.containsKey(pre-k)){
                count+=map.get(pre-k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

那么,这篇文章就到此为止啦,希望能帮助到大家
博主才疏学浅,如有错误,请指正文章来源地址https://www.toymoban.com/news/detail-415721.html

到了这里,关于剑指 Offer II 010. 和为 k 的子数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法:给你一个整数数组 nums 和一个整数k,请你统计并返回该数组中和为 k 的子数组的个数

    Java面试题目录 算法:给你一个整数数组 nums 和一个整数k,请你统计并返回该数组中和为 k 的子数组的个数 使用前缀和来实现。在保存累加和的数组preSum中,找坐标大的元素与坐标小的元素差值正好为k的个数。 leecode地址:. - 力扣(LeetCode) 直接在力扣找了个写好的答案。

    2024年01月24日
    浏览(48)
  • 和为 K 的子数组——前缀和+哈希

    题目链接:力扣 注意:此题不能使用滑动窗口,因为数组中可能会出现负数。也就是说右指针向后移1位不能保证区间会增大,左指针向后移1位也不能保证区间和会减小。给定左右指针的位置没有二段性 已知sum[i]是从nums[0~i]的和,sum[i-1]是nums[0~i-1]的和 则有 sum[i] - sum[i-1] =

    2024年02月16日
    浏览(42)
  • 560. 和为 K 的子数组【哈希、前缀和】

    560. 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1: 输入:nums = [1,1,1], k = 2 输出:2 示例 2: 输入:nums = [1,2,3], k = 3 输出:2 提示: 1 = nums.length = 2 * 104 -1000 = nums[i] = 1000 -107 = k = 107 C代码:哈希、前缀和

    2024年02月02日
    浏览(42)
  • hot100:10和为k的子数组

    题目链接: LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台 算法思想: 法一(暴力法): 使用两层for循环列举出所有的子数组,使用一个变量sum求得子数组的和并判断是否为k 法二(前缀和+哈希表): 前缀和:前缀和就是从下标为0的元素开始到当

    2024年01月23日
    浏览(43)
  • 【LeetCode热题100】【子串】和为 K 的子数组

    题目 给你一个整数数组  nums  和一个整数  k  ,请你统计并返回  该数组中和为  k   的子数组的个数  。 子数组是数组中元素的连续非空序列。 示例 1: 示例 2: 提示: 1 = nums.length = 2 * 104 -1000 = nums[i] = 1000 -107 = k = 107 暴力  直接两层循环找出所有连续子数组的和,这个

    2024年01月19日
    浏览(44)
  • 【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字

    盛水最多的容器 (1)暴力解法   算法思路:我们枚举出所有的容器大小,取最大值即可。   容器容积的计算方式:   设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定,因此可得容积公式 :

    2024年02月13日
    浏览(48)
  • [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解

    和为 K 的子数组 分析 :因为有 负数 的存在 无法使用\\\" 双指针 \\\"优化,因为 区间求和不具备单调性 可能已经找到前缀和为k的子数组了,但是后面仍然可能会有更长的和为k的子数组存在 思路 :前缀和 + 哈希表 前缀和 : 以 i 位置为结尾 的所有的子数组 将问题转化为 :在

    2024年04月28日
    浏览(32)
  • leetcode分类刷题:易混题辨析一、209. 长度最小的子数组 vs 560. 和为K的子数组

    1、刷题慢慢积累起来以后,遇到相似的题目时,会出现算法思路混淆了 2、这两道题都是对 连续子数组加和 进行考察,细节区别在于数组元素在209. 长度最小的子数组为 正整数(窗口增加元素递增,减少元素递减) ,在560. 和为K的子数组为 整数 3、209. 长度最小的子数组采

    2024年02月10日
    浏览(39)
  • 算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

    这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作 目录 4.除自身以外数组的乘积 4.1解析 4.2题解 5.和为K的子数组 5.1解析 5.2题解 6.和可被K整除的子数组 6.1解析 6.2题解 7.连续数组 7.1题解 7.2题解 8.矩阵区域和 8.1解析 8.2题解 4.除自身以外

    2024年04月14日
    浏览(43)
  • 剑指offer——数值的整数次方

    题目:实现函数 double Power(double base,int exponent),求base 的exponent 次方。不得使用库函数,同时不需要考虑大数问题 由于不需要考虑大数问题,这道题看起来很简单,可能不少应聘者在看到题目30秒后就能写出如下的代码: 运行结果为: 不过遗憾的是,写得快不一定就能得到面试

    2024年02月22日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包