209-长度最小的子数组

题目:

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

  输入:s = 7, nums = [2,3,1,2,4,3]
  输出:2
  解释:子数组 [4,3] 是该条件下的长度最小的子数组。

进阶:

  如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解答一

注意题目中的是连续的子数组,直接办法是遍历,从每个nums[i]出发,找到最短的超过target的值,然后记录最短的长度,代码如下:

//1-暴力搜索,超时
int minSubArrayLen(int s, vector<int>& nums) 
{
    int idx1 = 0;
    int minLen = INT_MAX;
    int sum = 0;
    while (idx1 < nums.size())
    {
        sum = nums[idx1];
        if (sum >= s)
            return 1;

        for (int idx2 = idx1 + 1; idx2 < nums.size(); idx2++)
        {
            sum += nums[idx2];
            if (sum >= s)
            {
                if (idx2 + 1 - idx1 < minLen)
                {
                    minLen = idx2 + 1 - idx1;
                    break;
                }
            }
        }

        idx1++;
    }

    return minLen == INT_MAX ? 0 : minLen;
}

时间复杂度O(n^2),空间复杂度:使用了额外的存储,为O(1)

提交后超时。。。

解答二

  提示:双指针、二分查找

  使用双指针:如果【idx1-idx2】的和超过target,则记录长度,然后向右移动idx1,如果此时还满足,则更新minLen;如果此时不满足了,则当前区间内的值小于target,则向右移动idx2直到满足,实时更新minLen,代码如下:

/双指针法,如果两个指针的范围内超过s,则右移idx1,如果不满足则右移idx2,
//记录最小的长度
int minSubArrayLen2(int s, vector<int>& nums)
{
    int minLen = INT_MAX;
    int idx1 = 0, idx2 = 0;
    int sum = 0;
    while (idx2 < nums.size())
    {
        sum += nums[idx2];
        while (sum >= s)
        {
            if (idx2 - idx1 + 1 < minLen)
                minLen = idx2 - idx1 + 1;

            sum -= nums[idx1];
            idx1++;
        }
            
        idx2++;
    }
    return minLen == INT_MAX ? 0 : minLen;
}

双指针相当于只遍历了一次,时间复杂度O(n),空间复杂度O(1)

解答三

看解答后,有一种方法为:前缀法+二分查找

原理:

  sum[i]表示从nums[0]到nums[i]的和,则 sum[i]-sum[j]  表示区间 [ j+1, i] 之间数字的和,然后在查找target时,即:sum[i] - sum[j] >= target ,即:寻找 i 使得: sum[i] >= target+ sum[j]

  而输入数组都是正整数,则 sums 数组一定是递增的,可以用二分查找法找到符合的值

代码:

//vec是递增的数组,target是目标值,找到值大于等于target的最小下标
//二分查找
int findBound(vector<int>& vec, int left, int right, int target)
{
    int l = left, r = right;
    int mid = -1;
    
    while (l<r)
    {
        mid = (l + r) >> 1;

        if (vec[mid] >= target)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }

    return vec[l] >= target ? l : -1;
}
int minSubArrayLen3(int s, vector<int>& nums)
{
    int ans = INT_MAX;
    int length = nums.size();
    vector<int> sums(length + 1, 0);
    for (int i = 1; i <= length; i++)
    {
        sums[i] = sums[i - 1] + nums[i-1];
    }

    //sum = nums[i] + sums[i] - sums[k] > s
    for (int i = 1; i <= length; i++)
    {
        int target = s + sums[i - 1];
        int bound = findBound(sums, 0, sums.size() - 1, target);
        if (bound != -1)
        {
            if (bound - i + 1 < ans)
                ans = bound - i + 1;
        }
    }
    
    return ans == INT_MAX ? 0 : ans;
}

二分查找的时间复杂度:O(lgn),在循环内嵌套二分查找,时间复杂度为: O(nlgn)

空间复杂度,使用了一个sums数组,O(n)

 

<algorithm>中有一个函数:lower_bound,用于查找一个递增数组内,大于等于target的最小索引,可用于替换上面的findBound函数

 

上一篇:209. 长度最小的子数组


下一篇:周练(5)209. 长度最小的子数组