首页 > 其他分享 >Leetcode 和为k的子数组

Leetcode 和为k的子数组

时间:2024-03-26 21:57:20浏览次数:25  
标签:pre count nums int sum mp 数组 Leetcode

Day11 第一题

#######解题思路:两层循环,用暴力法解决(从不同起始位置开始的子数组)

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 和为k的子数组的个数计数器count
        int count = 0; 
        for(int j =0;j<nums.length;j++){
            int sum = 0;
            for(int i = j;i < nums.length;i++){
                sum = sum + nums[i];
                if(sum == k){
                    count++;
                }
            }
        }
        
        return count;    
    }
}
力扣官方解答:
public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

####### 巧妙的利用\(sum[i,j] = sum[0,j]- sum[0,i-1]\),所以有sum[i-1] = sum[j] - k,所以\(i-1<j\),即contains判断要在hashmap加上sum[j]之前。

标签:pre,count,nums,int,sum,mp,数组,Leetcode
From: https://www.cnblogs.com/xytang-mini-juan/p/18097704

相关文章

  • 代码随想录算法训练营day35 | leetcode 860. 柠檬水找零、406. 根据身高重建队列、452
    目录题目链接:860.柠檬水找零-简单题目链接:406.根据身高重建队列-中等题目链接:452.用最少数量的箭引爆气球-中等题目链接:860.柠檬水找零-简单题目描述:在柠檬水摊上,每一杯柠檬水的售价为5美元。顾客排队购买你的产品,(按账单bills支付的顺序)一次购买一杯。每位顾客只买一......
  • LeetCode 11.盛最多的水(双指针,贪心)
    题目:思路:我们可以安排俩个指针(数组下标)放在数组的头部和尾部;每次移动高度较低的下标,判断是否为最大水量并记录;(水量=下标差乘较小高度)证明可行性:如果移动高度较高的下标,由于下标差减小,故不论后面下标对应的高度增大,不变或减小都会导致水量减小;(增大:下标差减小,较小高度......
  • 小阳同学刷题日记-209. 长度最小的子数组
        题目: 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl,numsl+1,...,numsr-1,numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。    惯例,献上我自......
  • LeetCode刷题Day11(补卡)
    20.有效的括号题目链接:leetcode20.有效的括号文章讲解:代码随想录视频讲解:哔哩哔哩视频这题考察的是栈的使用,遍历字符串,如果是左括号存入栈中,如果是右括号则对比栈的头部是否为与之匹配的左括号,如果不是则返回false,最后若栈为空则正好匹配返回true,详细代码如下:cl......
  • leetcode:链表的中间节点
    快慢指针快的到了末尾,慢的所指的就是中点你一开始写的时候while里面,fast.next放在前面,报错,空指针应该写在后面,对于偶数个元素的链表而言/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode......
  • 数据结构-数组
    数组是一种最为常见和应用广泛的数据结构,不用语言的数组不太一样,对于js的数组来说,和python的列表极其类似,都是可动态拓展值和类型的,还是来大致总结一下这个基础数据结构.创建数组letarr1=newArray('a','b',66)letarr2=['a','b',66]console.log(arr1......
  • 十八 1265. 数星星 (树状数组)
    1265.数星星(树状数组)思路:本题要统计每个星星左下角星星的数目,由于星星按y坐标增序给出,y坐标相同的按x坐标增序给出,所以不用关注y,可以视作每个x位置有几颗星星就为几的数组,每次统计左侧前缀和,再将当前计算的星星x位置数加一,使用树状数组(推荐视频:五分钟丝滑动画讲解|树状数......
  • 代码随想录算法训练营day34 | leetcode 1005. K 次取反后最大化的数组和、134. 加油站
    目录题目链接:1005.K次取反后最大化的数组和-简单题目链接:134.加油站-中等题目链接:135.分发糖果-困难题目链接:1005.K次取反后最大化的数组和-简单题目描述:给你一个整数数组nums和一个整数k,按以下方法修改该数组:选择某个下标i并将nums[i]替换为-nums[i]。重......
  • LeetCodeHot100 数组 53. 最大子数组和 56. 合并区间 238. 除自身以外数组的乘积
    53.最大子数组和https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-likedpublicintmaxSubArray(int[]nums){int[]dp=newint[nums.length];dp[0]=nums[0];for(inti=1;i<nums......
  • 第三篇-Javascript数组
    什么是数组数组指一组有序数据的集合,其中的每个数据被称作元素,在数组中可以存放任意类型的元素。可以通过new关键字来创建数组。Javascript访问数组1、通过索引访问单个元素:letarr=[1,2,3,4,5];console.log(arr[0]);//输出1console.log(arr[2]);//输出3cons......