LintCode 406: Minimum Size

题目描述

给定一个由 n 个整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。

样例

给定数组[2,3,1,2,4,3]和s = 7, 子数组[4,3]是该条件下的最小长度子数组。

Thu Feb 23 2017

思路

数组的题一般都是用指针扫描的。

这里是用一前一后两个指针都从左往右移，前面的指针一直移直到和大于s为止；后面的指针此时一直右移，直到距离最短为止。

时间复杂度是\(O(n)\).

代码

// 和大于S的最小子数组

int minimumSize(vector<int> &nums, int s)

{

    if (nums.size() <= 0) return -1;

    int l = 0, r = 0, sum = nums[0], ans = 6e5;

    while(1)

    {

        if (sum >= s)

        {

            if (r - l + 1 < ans)

            {

                ans = r - l + 1;

            }

            else

            {

                sum -= nums[l];

                ++l;

            }

        }

        else

        {

            sum += nums[r+1];

            ++r;

        }

        if (r == nums.size() || l > r) break;

    }

    if (ans == 6e5) return -1;

    return ans;

}

巴特西

LintCode 406: Minimum Size

LintCode 406: Minimum Size

题目描述

Thu Feb 23 2017

思路

代码

最新文章

热门文章