【错题集-编程题】dd爱框框(同向双指针 / 滑动窗口)

简介: 【错题集-编程题】dd爱框框(同向双指针 / 滑动窗口)

题目链接:dd爱框框 (nowcoder.com)


一、分析题目

同向双指针(其实也就是滑动窗口)。

  • 进窗口(sum += arr[right])
  • 判断(sum >= x)
  • 更新结果(right-left+1 < retlen   retl = left   retr=right)
  • 出窗口(sum -= arr[left])

二、代码

1、自己 AC 的代码

//没看题解之前AC的代码
#include <iostream>
using namespace std;
 
const int N=1e7+10, INF=1e9+7;
int a[N];
 
int main()
{
    int n, x;
    cin >> n >> x;
    for(int i=1; i<=n; i++) cin >> a[i];
    int sum=0;
    int len=INF;
    int i=1;
    int l=1, r=1;
    for(int j=1; j<=n; j++)
    {
        sum+=a[j];
        while(sum>=x)
        {
            if(j-i+1<len)
            {
                len=j-i+1;
                l=i, r=j;
            }
            sum-=a[i];
            i++;
        }
    }
    cout << l << ' ' << r << endl;
    return 0;
}
 
//看了题解之后AC的代码
#include <iostream>
using namespace std;
 
const int N=1e7+10;
int a[N];
 
int main()
{
    int n, x;
    cin >> n >> x;
    for(int i=1; i<=n; i++) cin >> a[i];
    int sum=0;
    int len=N;
    int i=1, j=1;
    int left=1, right=1;
    while(j<=n)
    {
        sum+=a[j];
        while(sum>=x)
        {
            if(j-i+1<len)
            {
                len=j-i+1;
                left=i, right=j;
            }
            sum-=a[i++];
        }
        j++;
    }
    cout << left << ' ' << right << endl;
    return 0;
}

2、值得学习的代码

#include <iostream>
using namespace std;
 
const int N = 1e7 + 10;
int arr[N];
int n, x;
 
int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    int left = 0, right = 0, sum = 0;
    int retLen = N, retLeft = -1, retRight = -1;
 
    while(right <= n)
    {
        sum += arr[right];
        while(sum >= x)
        {
            if(right - left + 1 < retLen)
            {
                retLeft = left;
                retRight = right;
                retLen = right - left + 1;
            }
            sum -= arr[left++];
        }
        right++;
    }
 
    cout << retLeft << " " << retRight << endl;
 
    return 0;
}

三、反思与改进

这道题一看完,我的第一反应是前缀和,因为题目给的公式和前缀和很像,于是就往前缀和方向去想了,最后只过了 20% 的样例,我认为是数据范围的关系(因为按照题目所给的数据范围,前缀和是会超时的)。总不可能用两层 for 循环嵌套暴力解法吧,肯定超时(果然,也是只过了 20% 的样例)。于是,大脑开始飞速运转,联想到前几天好像做到一题很类似的(刚刚去查了一下,发现考察内容基本一样:209. 长度最小的子数组 - 力扣(LeetCode),我晕),在写这道题目时,想到了思路,也知道可以减少比较次数的位置,但还是没能绕开两层 for 循环这个结构,其实滑动窗口就是在暴力解法上进行优化的。本质还是对滑动窗口掌握不熟练,还有就是总喜欢固定思维让 i 先遍历,然后 j 在 i 后面遍历,这道题目可以让 j 先遍历,然后 i 在 j 之前遍历,就可以起到 “剪枝” 的作用了。但这道题如果数组中有负数,就得采用前缀和了。


相关文章
|
6月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
6月前
|
C++
【编码狂想】指针航行,链表魔法,解锁结构体和类的编程幻境
【编码狂想】指针航行,链表魔法,解锁结构体和类的编程幻境
83 1
|
6月前
|
算法 Linux C语言
【Linux系统编程】深入理解Linux目录操作:文件夹位置指针操作函数(telldir,seekdir,rewinddir)
【Linux系统编程】深入理解Linux目录操作:文件夹位置指针操作函数(telldir,seekdir,rewinddir)
78 0
|
5月前
|
存储 安全 编译器
【C++航海王:追寻罗杰的编程之路】引用、内联、auto关键字、基于范围的for、指针空值nullptr
【C++航海王:追寻罗杰的编程之路】引用、内联、auto关键字、基于范围的for、指针空值nullptr
66 5
|
5月前
|
Go C++
代码随想录——双指针/滑动窗口(二)
代码随想录——双指针/滑动窗口(二)
|
5月前
|
算法
双指针+滑动窗口
双指针+滑动窗口
|
5月前
|
Go C++
代码随想录——双指针与滑动窗口(四)
代码随想录——双指针与滑动窗口(四)
|
5月前
|
Go C++
代码随想录——双指针/滑动窗口(三)
代码随想录——双指针/滑动窗口(三)
|
6月前
|
C语言
文件类型指针及其在编程中的应用
文件类型指针及其在编程中的应用
99 0
|
6月前
|
存储 编译器 C语言
数组指针,高效编程之道
数组指针,高效编程之道