首页 > 试题广场 >

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

[编程题]未排序正数数组中累加和为给定值的最长子数组的长度

热度指数：7068 时间限制：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

输出

备注:

算法知识视频讲解

查看答案及解析

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int Max=0, s=a[0];
    for(int l=0,r=0;r<n;){
        if(s==k){
            Max = max(Max, r-l+1);
            s -= a[l++];
        }else if(s<k){
            r++;
            if(r==n)
                break;
            s += a[r];
        }else
            s -= a[l++];
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2020-02-02 00:37:12 回复(0)

专业犯错者

题目描述有误，应该更正为：求连续最长数组和为k的子数组长度。

编辑于 2020-03-31 16:06:19 回复(1)

Java

pein531

滑动窗口求解，抠边界还挺烦的，总有些诡异的错误

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(params[i]);
        int left = 0, right = 0, sum = 0, maxLen = 1;
        while(right < n){
            sum += arr[right];
            if(sum < k){
                right ++;
            }else if(sum > k){
                while(left < right && sum > k){
                    sum -= arr[left];
                    left ++;
                }
                if(sum == k) maxLen = Math.max(maxLen, right - left + 1);
                right ++;
            }else{
                maxLen = Math.max(maxLen, right - left + 1);
                sum -= arr[left];
                left ++;
                right ++;
            }
        }
        System.out.println(maxLen);
    }
}

发表于 2021-12-02 21:20:18 回复(0)

犯困的小山竹在找内推

运行时间：98ms
超过94.24%用Java提交的代码

占用内存：20544KB

超过95.84%用Java提交的代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{

public static void main(String[] args) throws IOException{
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
String[] inputData = sc.readLine().split(" ");
int len = Integer.parseInt(inputData[0]);
int target = Integer.parseInt(inputData[1]);
String[] inputData2 = sc.readLine().split(" ");
int[] matrix = new int[len];
for(int i = 0; i< len; i++){
matrix[i] = Integer.parseInt(inputData2[i]);
}

int left = 0;
int right = 0;
int maxLen = 0;
int sum = 0;
while(left<len&&right<len){
sum+=matrix[right];
if(sum == target){
maxLen = Math.max(right-left+1,maxLen);
sum-=matrix[left];
left++;
right++;
}
else if(sum<target){

right++;
}
else{
sum-=matrix[left];
sum-=matrix[right];
left++;

}
}
System.out.println(maxLen);



}
}

发表于 2021-03-19 12:39:17 回复(0)

C/C++

ccsvtbcsk

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int n,k,sum=0;
scanf("%d %d",&n,&k);
vector<int> d(n);
for(int i=0;i<n;++i) scanf("%d",&d[i]);
int i=0,j=0,res=0;
while(j<n){
while(j<n&&sum<k)sum+=d[j++];
if(sum<k) break;
else if(sum==k) {
res=max(res,j-i);
sum-=d[i++];
}else{
while(i<j&&sum>k) sum-=d[i++];
if(sum==k) res=max(res,j-i);
}
}
printf("%d\n",res);
return 0;
}

发表于 2020-09-24 17:28:11 回复(0)

是兄弟就一起加班

C++类滑动窗口

看了半天发现题有问题，，，应该是连续子数组啊，那不然O(n)个棒槌

这个题解法类似滑动窗口，由于都是正数，小了就向右移动右边界，大了就向右移动左边界

窗口内元素和等于目标值时，更新答案，最后输出答案即可

贴个代码摸个鱼

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin>>n>>k;
    if(n<1 || k<0)
        return 0;
    vector<int> v(n, 0);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }
    int left=0, right=0, sum=v[0], res=0;
    while(right < n){
        if(sum == k){
            res = max(res, right-left+1);
            sum -= v[left];
            ++left;
        }
        else if(sum < k){
            ++right;
            if(right == n)
                break;
            sum += v[right];
        }
        else{
            sum -= v[left];
            ++left;
        }
    }
    cout<<res<<endl;
    return 0;
}

编辑于 2020-07-18 10:53:12 回复(0)

秃头一半

#include<iostream>
(720)#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    int inp[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &inp[i]);
    }
    int left = 0, right = 0;
    int sum = inp[0];
    int count = 0;
    while(right < n){
        if(sum == k){
            count = max(count,right - left + 1);
            sum -= inp[left];
            left++;
        }
        else if(sum > k){
            sum -= inp[left];
            left++;
        }
        else if(sum < k){
            right++;
            if(right >= n){
                break;
            }
            else
                sum += inp[right];
        }
    }
    cout<<count<<endl;
    return 0;
}

发表于 2020-05-01 13:50:27 回复(0)

offer之神降临吧

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for(int i = 0; i < n; i ++)
        cin >> arr[i];
    int Max = 0;
    int temp = k;
    int len = 0;
    int start=0, end = 0;
    while(end < n){
        temp -= arr[end];
        if(temp > 0)
            end++;
        else if(temp < 0){
            temp += arr[start];
            start++;
            temp += arr[end];
        }
        else{
            len = end - start + 1;
            Max = max(Max, len);
            temp += arr[start];
            start++;
            end++;
        }
    }
    cout << Max << endl;
}

双指针法，计算start和end指针之间的数字和，

如果等于k，则计算长度，并start++，end++；

如果小于k ，则end++；

如果大于k，则start++。

发表于 2020-05-01 11:01:01 回复(0)

今天您offer了吗

#include <iostream>
#include <vector>

using namespace std;

// 给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度
// 例如，arr = [1, 2, 1, 1, 1], k = 3
// 累加和为3的最长子数组为[1, 1, 1]，所以结果返回3
// [要求]
// 时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

/**
 * 双指针法,通过sum变量和left,right来保持一个滑动窗口
 */
int ksum(){
    int n,k;
    cin>>n>>k;

    if(n==0){
        return 0;//如果传入的n为0，直接返回0
    }
    
    vector<int> nums;
    for (int i = 0; i < n; i++)
    {
        int tmp ;
        cin >> tmp;
        nums.push_back(tmp);
    }

    if(n==1){
        return nums[0] == k ? 1 : 0;//如果只有一个数，比较这个数和k的大小即可
    }

    int sum;
    int len = 0;

    int left = 0,right = 0;
    sum = nums[left];

    while (left <= right && right < n-1)//循环结束条件是right到达倒数第二个元素
    {
        if(sum == k){
            len = max(len,right-left+1);//取较大值
            right++;
            sum=sum+nums[right]-nums[left];//滑动窗口整体向右移动一个单位
            left++;
        }else if(sum < k){
            right++;
            sum+=nums[right];//滑动窗口右界向右移动一个单位
        }else{
            sum-=nums[left];
            left++;//滑动窗口左届向右移动一个单位
        }
    }
    
    return len;
}

int main(void){
    cout << ksum() << endl;
}

发表于 2019-11-23 14:59:01 回复(0)

Java

小星教授

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
       
        int start = 0,end = 0,sum=0,maxLen = Integer.MIN_VALUE;
        while(start<n && end<n){
            while(end<n){
                sum += arr[end++];
                if(sum==k){
                    maxLen = Math.max(maxLen,end-start);
                }else if(sum > k){
                    break;
                }
            }
            
            while(start < n){
                sum -= arr[start++];
                if(sum==k){
                    maxLen = Math.max(maxLen,end-start);
                }else if(sum < k){
                    break;
                }
            }
            
        }
        System.out.print(maxLen);
		
	}
}

发表于 2019-10-24 12:14:57 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
	int left = 0, right = 0, sum = num[0], len = 0;
	while (right<n){
		if (sum < k){
			right++;
			if (right == n)
				break;
			sum += num[right];
		}
		else if (sum > k)
			sum -= num[left++];
		else{
			len = max(len, right - left + 1);
			sum -= num[left++];
		}
	}
    cout<<len<<endl;
    return 0;
}

发表于 2019-08-24 22:04:48 回复(3)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int left = 0;
        int right = 0;
        int sum = arr[left];
        int len = 0;

        while (right < n) {
            if (sum == k) {
                len = Math.max(right - left + 1, len);
                sum -= arr[left++];
            } else if (sum > k) {
                sum -= arr[left++];
            } else {
                right++;
                if (right == n) {
                    break;
                }
                sum += arr[right];
            }
        }

        System.out.println(len);
    }
}

发表于 2019-10-10 17:12:42 回复(0)

Allen2023wp

N,k = map(int,input().split())

arr = list(map(int,input().split()))

i = 0

start = 0

length = 0

for m in range(len(arr)):

i += arr[m]

while i > k:

i = i - arr[start]

start += 1

if i == k and m -start +1 > length:

length = m -start +1

print(length)

发表于 2023-06-14 19:15:11 回复(0)

Java

寄居的过客

import java.io.*;
import java.util.LinkedList;
import java.util.Deque;
public class Main{
public static void main(String[] args) throws IOException{
// Deque<Integer> dq = new LinkedList<>();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int l = Integer.valueOf(s[0]);
int target = Integer.valueOf(s[1]);
s = reader.readLine().split(" ");

int[] arr = new int[l];
for(int i = 0;i< l;i++){
arr[i] = Integer.valueOf(s[i]);
}
int sum=arr[0],length=0,max=0;
int left=0,right=0;
for(int i = 1;i<l;i++){
right++;
sum += arr[i];
if(sum>target){
while(sum>target){
sum-=arr[left];
left++;
}

}

//因为减去第一个可能造成出现刚好等于target的情况所以直接把判断 sum==target 放在下面避免多次判断

if(sum==target){
length = right-left+1;
max = Math.max(length,max);
sum -= arr[left];
left++;
}

}
System.out.println(max);
}

}

发表于 2022-08-11 11:13:40 回复(0)

C++

木子蓝色

直接套模板

# include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    int left = 0, right = 0;
    int sum = 0;
    int ans = 0;
    // 滑动窗口的最大窗口模板
    while(right < n){
        sum += nums[right];
        while(sum > k){            
            sum -= nums[left];
            left++;
        }
        // 多了这个 sum == k 的判断
        if(sum == k) ans = max(ans, right - left + 1);
        right++;
    }
    
    cout << ans << endl;
    return 0;
}

发表于 2022-04-07 10:19:51 回复(0)

C++

麦芒2021

子数组：连续

双指针，因为是等于，所以可能出现j不变，i++的情况；如果是小于等于，每次j都是+1；

注意：先加arr[i]或者arr[j]还是i++或j++；

注意：当出现等于target时，如果数组中可能出现0，则需要仍然按照j++而非i++,j++处理。

#include "bits/stdc++.h"

using namespace std;
int main()
{
    int len;
    cin>>len;
    int target;
    cin>>target;
    vector<int> arr(len);
    int ret=0;//满足要求的最大长度
    int cur=0;//当前长度
    int i=0,j=0;
    int sum=0;
    for(int k=0;k<len;k++)
    {
        cin>>arr[k];
    }
    while(i<len)
    {
        if(j>=len){sum-=arr[i];if(sum==target){ret=max(ret,len-i);}i++;continue;}
        else if(sum+arr[j]>target){sum-=arr[i];i++;}
        else if(sum+arr[j]==target){ret=max(ret,j-i+1);sum+=arr[j];
                                    //sum-=arr[i];i++;
                                    j++;}
        else if(sum+arr[j]<target){sum+=arr[j];j++;}
        //cout<<sum<<' ';
    }
    cout<<ret;
    return 0;
}

发表于 2022-01-10 12:35:12 回复(0)

Python

编号3207

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)

静静流淌

import java.util.*;
public class Main{
        public static void main(String [] args){
            Scanner input = new Scanner(System.in);
            int N,k;
            N = input.nextInt();
            k = input.nextInt();
            int [] arr = new int[N];
            for(int i = 0;i < N;++i)
                arr[i] = input.nextInt(); 
            int left = 0;
            /* 注意如果sum初始化为0，right的初始化从-1开始，
               注意终止条件的判定，注意初始化条件。
            */
            int right = -1;     
            int sum = 0;
            int maxlen = 0;
            while(right < N){
                if(sum == k){
                    maxlen = Math.max(maxlen,right-left+1);
                    sum -= arr[left];
                    ++left;
                }else if(sum < k){
                    ++right;
                    if(right == N)
                        break;
                    sum += arr[right];
                }else{
                    sum -= arr[left];
                    ++left;
                }
            }
            System.out.printf("%d\n",maxlen);
        }
}

发表于 2021-03-25 08:59:59 回复(0)

Java

眼睛想旅行121

import java.util.Scanner;

public class Main{
    public static int getMaxLength(int[] arr,int k){
        if(arr==null||arr.length==0||k<=0){
            return 0;
        }
        int left=0;
        int right=0;
        int sum=arr[0];
        int len=0;
        while (right<arr.length){
            if(sum==k){
                len=Math.max(len,right-left+1);
                sum-=arr[left++];
            }else if(sum<k){
                right++;
                if(right==arr.length){
                    break;
                }
                sum+=arr[right];
            }else{
                sum-=arr[left++];
            }
        }
        return len;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(getMaxLength(arr,k));
    }
}

发表于 2021-03-15 13:42:48 回复(0)