给定一个数组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)第一行不要加注释