hot100:10和为k的子数组

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

题目链接:

LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台

算法思想:

法一(暴力法):

使用两层for循环列举出所有的子数组,使用一个变量sum求得子数组的和并判断是否为k

//暴力解法
    public int subarraySum(int[] nums, int k) {
        int ret = 0;
        for(int i = 0;i < nums.length;i++) {
            int sum = 0;
            //因为某单个元素也是子数组,所以内层循环j=i
            for(int j = i;j < nums.length;j++) {
                sum += nums[j];
                if(sum == k) {
                    ret++;
                }
            }
        }
        return ret;
    }
法二(前缀和+哈希表):

前缀和:前缀和就是从下标为0的元素开始到当前下标之间所有元素的和(假设是一个数组arr的话,下标为i对应的前缀和就等于arr[0]+arr[1]+arr[2]+......+arr[i-1]+arr[i]),举一个列子:

假设给定一个数组为arr:{1,3,5,7,9}

前缀和数组就是sum:{1,4,9,16,25}

所以就可以推导出前缀和的公式:sum[i]=sum[i-1]+arr[i],如果计算给定下标范围(i,j)之间元素的和可以使用arr[i]+arr[i+1]+......+arr[j-1]+arr[j]=sum[j]-sum[i-1]

为了加深大家对前缀和的理解,这样附上一道有关前缀和的算法题: 【模板】前缀和_牛客题霸_牛客网

 代码如下:

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] array = new int[n+1];
        for(int i = 1;i <= n;i++) {
            array[i] = scanner.nextInt();
        }

        long[] dp = new long[n+1];
        for(int i = 1;i <= n;i++) {
            dp[i] = dp[i-1] + array[i];
        }

        while(q > 0) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            System.out.println(dp[r] - dp[l-1]);
            q--;
        }
    }
}

有了前缀和的知识来解决整个题目就会变得相对简单一点了,假设某个下标范围内(i,j)之间的和为k,那么根据前缀和可知sum[j]=sum[i-1]+k,经过简单移项之后可以得到sum[i-1]=sum[j]-k,那么整个问题就转换成了以j下标为基准,之前有几个子数组的前缀和为sum[j]-k,k是已知的,sum[j]可以使用相加的方式算出,通过遍历数组,计算每个位置的前缀和,并使用一个哈希表来存储每个前缀和出现的次数,在遍历的过程中,我们检查是否存在sum[j] - k的前缀和,如果存在,说明从某个位置到当前位置的连续子数组的和为k,我们将对应的次数累加到结果中

    //法二:前缀和+哈希表
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);

        int sum = 0;
        int ret = 0;
        for(int x : nums) {
            sum += x;//计算前缀和
            ret += map.getOrDefault(sum-k,0);//统计结果
            map.put(sum,map.getOrDefault(sum,0)+1);//更新map中的前缀和
        }
        return ret;
    }

 注意:这里需要预先在map中存入一次为0的前缀和,目的是为了防止下标从0开始累加到某一位时前缀和刚好时k,这样刚好存在一个子数组和为k,那么就会在map寻找sum-k=0的前缀和出现了几次,如果不提前预存一个的话就会漏掉一种结果。文章来源地址https://www.toymoban.com/news/detail-817722.html

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

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

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

相关文章

  • 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日
    浏览(44)
  • 【算法Hot100系列】搜索旋转排序数组

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年01月21日
    浏览(56)
  • 剑指 Offer II 010. 和为 k 的子数组

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 示例 2: 提示: 这个题目做出来不难,直接暴力枚举。但是利用哈希表和前缀和优化的过程我一直不是很理解,所以写下这篇文章来一点一点的研究,希望能对大家有所帮助 首先,先看最

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

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

    2024年02月10日
    浏览(39)
  • 【算法Hot100系列】寻找两个正序数组的中位数

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月03日
    浏览(38)
  • Leetcode-每日一题【剑指 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 前置知识 前缀和

    2024年02月15日
    浏览(48)
  • 【算法Hot100系列】在排序数组中查找元素的第一个和最后一个位置

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月02日
    浏览(49)
  • 【2023】LeetCode HOT 100——普通数组

    2023年08月26日
    浏览(42)
  • 【面试HOT100】子串&&普通数组&&矩阵

    系列综述: 💞目的:本系列是个人整理为了 秋招面试 的,整理期间苛求每个知识点,平衡理解简易度与深入程度。 🥰来源:材料主要源于LeetCodeHot100进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证。 🤭结语:如果有帮到

    2024年02月07日
    浏览(31)
  • 力扣hot100 打家劫舍 DP 滚动数组

    Problem: 198. 打家劫舍 👨‍🏫 参考地址 时间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( 1 ) O(1) O ( 1 )

    2024年01月19日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包