首页 > 试题广场 >

未排序正数数组中累加和为给定值的最长子数组的长度

[编程题]未排序正数数组中累加和为给定值的最长子数组的长度
  • 热度指数:7137 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组arr,该数组无序,但每个值均为正数,再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度
例如,arr = [1, 2, 1, 1, 1], k = 3
累加和为3的最长子数组为[1, 1, 1],所以结果返回3
[要求]
时间复杂度为,空间复杂度为


输入描述:
第一行两个整数N, k。N表示数组长度,k的定义已在题目描述中给出
第二行N个整数表示数组内的数


输出描述:
输出一个整数表示答案
示例1

输入

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))

编辑于 2021-12-05 21:49:19 回复(0)
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)
第一行不要加注释
编辑于 2019-08-13 09:00:02 回复(0)