这道题给定了我们一个数字,让我们求子数组之和大于等于给定值的最小长度。
- 先来看O(n)的解法:
- 我们需要定义两个指针left和right,分别记录子数组的左右的边界位置,初始都指向array[0], 然后我们让right向右移(子序列扩大),直到子数组和大于等于给定值或者right达到数组末尾,此时我们更新最短距离。
- 然后看看能不能得到更小的符合条件的子序列,将left像右移一位进行尝试,如果还是大于,继续left右移, 如果小于或等于(因为每个都是正数), 说明不可能有更小的了,只能整个window右移来尝试新机会。注意length == 1 的时候可以提前结束搜索。
代码如下:
//
// main.cpp
// leetcode
//
// Created by YangKi on 15/11/19.
// Copyright © 2015年 YangKi. All rights reserved.
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
using namespace std;
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int size = (int)nums.size();
if (size == 0)
{
return 0;
}
int left = 0;
int right = 0;
int length;
int sumOfWindow = nums[0];
// 先扩大(right 右移)
while (sumOfWindow < s)
{
right ++;
if (right > size - 1)
{
break;
}
sumOfWindow += nums[right];
}
if (right == size)
{// 说明全加一起也小于s
return 0;
}
// 否则,先确定一个窗口大小
length = right - left + 1;
// 接下来就是尝试有没有更小的窗口
while (right <= size -1)
{
// 尝试缩小(left 右移)
while (sumOfWindow - nums[left] >= s)
{
sumOfWindow -= nums[left];
left++;
length --;
if (length == 1)
{
return 1;
}
}
// 不能再缩小了,只能整体右移
if (right + 1 >= size)
{// 已经不能右移了
return length;
}
sumOfWindow = sumOfWindow - nums[left] + nums[right + 1];
left ++;
right ++;
}
return length;
}
};
网友评论