【LintCode 简单】838. 子数组和为K

╰+攻爆jí腚メ 2022-10-23 15:24 146阅读 0赞

1. 问题描述

给定一个整数数组和一个整数k，你需要找到连续子数列的和为k的总个数。

2. 样例

**样例1**

输入: nums = [1,1,1] 和 k = 2
    输出: 2
    解释:
    子数组 [0,1] 和 [1,2]

**样例2**

输入: nums = [2,1,-1,1,2] 和 k = 3
    输出: 4
    解释:
    子数组 [0,1], [1,4], [0,3] and [3,4]

3. 代码

方法一： 暴力枚举 但是使用Python方法会超时

class Solution:
        """
        @param nums: a list of integer
        @param k: an integer
        @return: return an integer, denote the number of continuous subarrays whose sum equals to k
        """
        def subarraySumEqualsK(self, nums, k):
            # write your code here
            count = 0
            for i in range(len(nums)):
                sub = 0
                for j in range(i, len(nums)):
                    sub += nums[j]
                    if sub == k:
                        count+=1
            return count

方法二：

利用字典存储值。 加上新数 - k = 出现过的和    ->   加上新数 - 出现过的和 = k

class Solution:
        """
        @param nums: a list of integer
        @param k: an integer
        @return: return an integer, denote the number of continuous subarrays whose sum equals to k
        """
        def subarraySumEqualsK(self, nums, k):
            # write your code here
            count=0
            dic={0:1}
            sub=0
            for i in range(len(nums)):
                sub+=nums[i]
                if (sub-k) in dic:
                    count+=dic[sub-k]
                if sub not in dic:
                    dic[sub]=1
                else:
                    dic[sub]+=1
            return count

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关和为K的子数组

给定一个数组在给定一个整数，我们如何找出数组中和为这个整数的子数组呢？问题给你一个整数数组nums和一个整数k,请你统计并返回该数组中和为k的连续子数组的个数。

迷南。/ 2024年04月07日 16:07/ 0 赞/ 71 阅读

相关 LintCode - 89 K数之和

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [89 · K数之和 - LintCode]

浅浅的花香味﹌/ 2023年10月12日 13:13/ 0 赞/ 1 阅读

相关【LintCode 简单】326. 滑动数独

1. 描述给定一个3×n3×n 的矩阵 `number`，并且该矩阵只含有1到9的正整数。考虑有一个大小为 3×33×3 滑动窗口，从左到右遍历该矩阵 `number

旧城等待，/ 2023年01月17日 07:42/ 0 赞/ 103 阅读

相关最大子数组和

/ 输入一个整数数组nums，请在其中找一个和最大的子数组动态规划定义dp数组：dp[i]是以num[i]结尾的最大子数组和 / public cla

矫情吗；*/ 2022年10月29日 10:28/ 0 赞/ 186 阅读

相关最大子数组和

/ 输入一个整数数组nums，请你在其中找一个和最大的子数组，返回这个子数组的和 dp[i]表示以nums[i]的最大子数组和状态 / public c

青旅半醒/ 2022年10月27日 13:49/ 0 赞/ 196 阅读

相关【LintCode 简单】838. 子数组和为K

1. 问题描述给定一个整数数组和一个整数k，你需要找到连续子数列的和为k的总个数。 2. 样例样例1 输入: nums = [1,1,1] 和 k =

╰+攻爆jí腚メ/ 2022年10月23日 15:24/ 0 赞/ 147 阅读

相关 Subarray Sum Equals K（C++和为K的子数组）

（1）map class Solution { public: int subarraySum(vector<int>& nums, i

骑猪看日落/ 2022年09月08日 10:26/ 0 赞/ 156 阅读

相关【LintCode 简单】488. 快乐数

1.问题描述：写一个算法来判断一个数是不是"快乐数"。一个数是不是快乐是这么定义的：对于一个正整数，每一次将该数替换为他每个位置上的数字的平方和，然后重复这个过程直到

今天药忘吃喽~/ 2022年06月01日 07:55/ 0 赞/ 226 阅读

相关【LintCode 简单】517. 丑数

1.问题描述：写一个程序来检测一个整数是不是`丑数`。丑数的定义是，只包含质因子 `2, 3, 5` 的正整数。比如 6, 8 就是丑数，但是 14 不是丑数以为

￡神魔★判官ぃ/ 2022年06月01日 05:50/ 0 赞/ 207 阅读

相关【LintCode 简单】138. 子数组之和

1.问题描述：给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 2.样例：给出 `[-3, 1, 2, -3, 4]

ゞ浴缸里的玫瑰/ 2022年06月01日 00:10/ 0 赞/ 195 阅读