程序员代码面试指南---008未排序正数数组中累加和为给定值的最长子数组的长度

题目描述

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

输入描述

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

输出描述

输出一个整数表示答案

示例

输入： 5 3 1 2 1 1 1 输出： 3

备注

1⩽N⩽10^5 1⩽k⩽10^9 1⩽arri⩽100

解题思路

使用滑动窗口来实现。具体使用双指针来实现。

1、当滑动窗口的值等于k：滑动窗口左边界向右移动 2、当滑动窗口的值小于k：滑动窗口右边界向右移动 3、当滑动窗口的值大于k：滑动窗口左边界向右移动

代码实现

/* * @Description: 未排序正数数组中累加和为给定值的最长子数组的长度 * @Author: * @Date: 2020-10-22 16:18:11 * @LastEditTime: 2020-10-22 16:44:43 * @LastEditors: Please set LastEditors */ #include<iostream> #include<vector> #include<algorithm> 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_len = 0; //子数组的最大长度 int left = 0; //左指针 int right = 0; //右指针 int sum = arr[0]; //滑动窗口的大小 while(right < N){ if(sum == k){ //此时滑动窗口等于给定的值 max_len = max(max_len, right - left + 1); sum -= arr[left]; left++; //滑动窗口左边界向右移动 }else if(sum < k){ //此时滑动窗口的值小于给定的值 right++; //右边界移动一位 if(right == N){ // 超出边界，结束循环 break; } sum +=arr[right]; }else{ //此时滑动窗口的值大于给定的值 sum -= arr[left]; left++; // 左边界移动 } } cout << max_len << endl; //system("pause"); return 0; }