题解|dd爱框框

dd爱框框

题目分析:找出一个最短的区间,该区间的和大于等于x。返回区间的左右端点。如果有两个区间都满足要求且长度一样,则返回左区间小的。

读完题,就是滑动窗口了。

1.我们定义两个指针,left和right,用这两个指针维护一个窗口。right遍历数组的过程,就是让数组元素进窗口的过程,同时统计窗口的和。

2.如果窗口的和大于等于x了,此时就更新结果(区间长度),但是在更新结果的时候要判断这个结果是否比上一次小,如果小就更新,反之不更新。

3.更新之后,我们让left位置的元素出窗口,即窗口和减去left对应元素,如果和依旧小于,那么继续判断是否需要更新结果。

重复上面步骤,直到right走到结束。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main()
{
    int n = 0, x = 0;
    cin >> n >> x;
    vector<int> nums(n + 1);
    for (int i = 1; i <= n; ++i) cin >> nums[i];

    int left = 0, right = -1, sum = 0; //维护窗口信息
    int ret = INT_MAX, l = 0, r = 0; //记录结果
    while (right < n - 1)
    {
        sum += nums[++right];
        while (sum >= x)
        {
            if (ret > right - left + 1)
            {
                ret = right - left + 1;
                l = left;
                r = right;
            }
            sum -= nums[left++];
        }
    }

    cout << l << " " << r << endl;
    return 0;
}

全部评论

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
07-02 22:46
门头沟学院 Java
码农索隆:hr:“管你投没投,先挂了再说”
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务