【python程序员代码面试指南】未排序正数数组中累加和为给定值

题目：给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度

  例如，arr = [1, 2, 1, 1, 1], k = 3 ，累加和为3的最长子数组为[1, 1, 1]，所以结果返回3 。[要求]  时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)。

分析：采用遍历一次数组，然后分别判断符合该情况的数组的长度。

code：

#[n,k] = list(map(int,input().split()))

#inp = list(map(int,input().split()))

[n, k] = 5, 3

inp =  [1, 2, 1, 1, 1]

maxLen = 0

Sum = 0

l = 0

for i in range(len(inp)):

    Sum += inp[i]

    if (Sum > k):

        Sum -= inp[l]

        l += 1

    if Sum == k:

        if i - l + 1 > maxLen:

            maxLen = i - l + 1

print(maxLen)

程序运行结果：

3