给定一个数组arr,该数组无序,但每个值均为正数,再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度
例如,arr = [1, 2, 1, 1, 1], k = 3
累加和为3的最长子数组为[1, 1, 1],所以结果返回3
[要求]
时间复杂度为
,空间复杂度为
第一行两个整数N, k。N表示数组长度,k的定义已在题目描述中给出
第二行N个整数表示数组内的数
输出一个整数表示答案
5 3 1 2 1 1 1
3
line1 = input()
line2 = input()
line1_ary = line1.split(' ')
n = int(line1_ary[0])
k = int(line1_ary[1])
strs1 = line2.split(' ')
def get_sum(left, right):
result = 0
for i in range(left, right+1):
result += int(strs1[i])
return result
def test_max_length(strs, k):
left = 0
right = 0
n = len(strs)
sum = int(strs[0])
max_len = -1
while right < n:
if sum == k:
if right - left + 1 >max_len:
max_len = right - left + 1
right += 1
if right < n:
sum += int(strs1[right])
elif sum < k:
right += 1
if right < n:
sum += int(strs1[right])
else:
if left + 1 > right:
right += 1
if right < n:
sum += int(strs1[right])
sum -= int(strs1[left])
left += 1
return max_len
print(test_max_length(strs1, k)) N, k = map(int, input().split()) ls = list(map(int, input().split())) index = 0 #最大子数组开始的索引值 max_len = 1 #初始化最大长度值为1 curr_sum = 0 #当前子数组的和 #遍历列表ls for i in range(N): curr_sum += ls[i] while curr_sum > k: curr_sum -= ls[index] index += 1 #当前子数组的和去掉头元素后,索引要更新 if curr_sum == k: max_len = max(max_len, i-index+1) #比较当前子数组(和为k)的长度是否比最大长度要大 print(max_len)第一行不要加注释