和为K的连续子数组

[编程题]和为K的连续子数组

热度指数：19104 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序数组 arr , 其中元素可正、可负、可0。给定一个整数 k ，求 arr 所有连续子数组中累加和为k的最长连续子数组长度。保证至少存在一个合法的连续子数组。

[1,2,3]的连续子数组有[1,2]，[2,3]，[1,2,3] ，但是[1,3]不是

数据范围： $1 \le n \le 10^5$ ， $|val| \le 100$ ， $|k| \le 10^9$
要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[1,-2,1,1,1],0

输出

示例2

输入

[0,1,2,3],3

输出

备注:

算法知识视频讲解

Python3

Oliver1234

对于每个arr[i],将前缀和arr[0]+......+arr[i]，以及i存入字典的key，value中
如果两个前缀和的差值为k，说明它们中间那段子数组的和为k。我们可以通过两个index的差值得到子数组长度
class Solution:
    def maxlenEqualK(self , arr: List[int], k: int) -> int:
        # write code here
        d = {0:-1} # d记录前缀和，以及该前缀和对应的最小index
        total, maxlen = 0, 0 # total记录前缀和，maxlen记录最大长度
        for i in range(len(arr)):
            total += arr[i] # 更新前缀和
            if total-k in d:# 如果有前缀和等于total-k，说明中间连续子串之和为k
                if maxlen < i-d[total-k]: maxlen = i-d[total-k] # 子数组长度为index的差值，并更新maxlen
            if total not in d: # 如果该前缀和已存在，则只保留之前最小的index
                d[total] = i # 如果不存在，将前缀和及其index计入d，
        return maxlen

发表于 2022-02-02 16:46:47 回复(0)

Python3

Joy_9

class Solution:
    def maxlenEqualK(self , nums: List[int], k: int) -> int:
        # write code here
        dic={}
        max_len,sum_v=0,0
        dic[0]=-1
        for i in range(len(nums)):
            sum_v+=nums[i]
            if (sum_v-k in dic.keys()):
                max_len=max(i-dic[sum_v-k],max_len)
            if sum_v not in dic.keys():
                #重复也保留最小的那一个
                dic[sum_v]=i
        return max_len

发表于 2022-01-19 04:35:23 回复(1)

Python3

牛客334257037号

class Solution:
def maxlenEqualK(self , arr , k ):
# write code here
Hashtable = {0: -1}
length, total = 0, 0
for i in range(len(arr)):
total = total + arr[i]
if total - k in Hashtable:
length = max(length, i - Hashtable[total - k])
if total not in Hashtable:
Hashtable[total] = i
return length

发表于 2021-08-13 20:48:50 回复(1)