为了解决这个问题,我们可以使用滑动窗口的方法。滑动窗口可以让我们在不需要嵌套循环的情况下遍历序列中所有的连续子序列。
以下是这个方法的步骤:
- 初始化两个指针
start
和end
,都指向序列的开始。 - 初始化当前和
current_sum
为 0。 - 移动
end
指针,每次移动都将end
指向的值加到current_sum
。 - 如果
current_sum
大于sum
,移动start
指针,每次移动都从current_sum
中减去start
指向的值,直到current_sum
小于或等于sum
。 - 如果在任何时刻
current_sum
等于sum
,更新最长子序列的长度。 - 如果
end
到达序列的末尾,结束循环。 - 返回最长子序列的长度,如果没有找到,则返回 -1。
让我们把这个逻辑转换成 Python 代码:
def max_subsequence_length(sequence, target_sum):
start = end = current_sum = 0
max_length = -1
while end < len(sequence):
current_sum += sequence[end]
while current_sum > target_sum and start < end:
current_sum -= sequence[start]
start += 1
if current_sum == target_sum:
max_length = max(max_length, end - start + 1)
end += 1
return max_length
# 示例
sequence = [1, 2, 3, 4, 2]
sum_to_find = 6
print(max_subsequence_length(sequence, sum_to_find)) # 输出: 3
sequence = [1, 2, 3, 4, 2]
sum_to_find = 20
print(max_subsequence_length(sequence, sum_to_find)) # 输出: -1
在这个代码中,我们通过不断地调整 start
和 end
指针的位置来找到所有可能的连续子序列,并检查它们的和是否等于 sum
。如果找到了和为 sum
的子序列,我们就更新最长子序列的长度。如果到最后都没有找到,就返回 -1。
'''有N个正整数组成的一个序列。给定整数sum,求长度最长的连续子序列a,使他们的和等于sum,返回此子序列的长度,如果没有满足要求的序列,返回-1。
输入描述:
序列:1,2,3,4,2 sum: 6
输出描述:
序列长度:3
补充说明:
输入序列仅由数字和英文逗号构成,数字之间采用英文逗号分隔;序列长度:1<=N<=200;
输入序列不考虑异常情况,由题目保证输入序列满足要求。
示例1输入:
输入描述:
序列:1,2,3,4,2
sum: 6
输出:3
说明:
解释: 1,2,3和4,2两个序列均能满足要求,所以最长的连续序列为1,2,3,因此结果为3
示例2输入:
序列: 1,2,3,4,2
sum: 20
输出: -1
自己实现
def max_subsequence(lists, sum):
slow = fast = cur_sum = 0
current_max_subseq = -1
while fast < len(lists):
# 计算快慢指针的sum
cur_sum += lists[fast]
if cur_sum > sum:
cur_sum -= lists[slow]
slow += 1
if cur_sum == sum:
cur_len = fast - slow + 1
# 有多个子序列的时候,取最大的
current_max_subseq = max(cur_len,current_max_subseq)
# fast指针到最后的时候,返回最大子序列
if fast == len(lists) - 1:
return current_max_subseq
fast += 1
return -1
标签:end,max,sum,长子,current,start,序列
From: https://www.cnblogs.com/njfl/p/18179809