当前位置：首页 > news >正文

算法学习日记 | 双指针

news 2026/5/12 12:27:12

🧠 算法学习日记 | 今天我用「双指针」解了三道题，原来“左右夹击”能这么高效！

大家好，我是你们的算法学习搭子 👋
今天继续我的算法入门之旅，重点练习了**双指针（Two Pointers）**这一高效的数据遍历技巧。

很多人觉得“双指针”只是用来判断回文的工具，但其实，它是一种空间换时间、动态调整窗口的经典思想。
我们用两个指针同时从两端或前后移动，避免重复计算，大幅提升效率。

今天我完整做了三道题，每一道都坚持用最朴素的双指针逻辑实现。下面我把题目原文和我的原始代码原封不动贴出来，不做任何删减或美化，只为真实记录学习过程。

🔹 题目一：回文判定

题目描述
给定一个长度为 $ n $ 的字符串 $ S $。请你判断字符串 $ S $ 是否是回文。

输入描述
输入仅 1 行包含一个字符串 $ S $。
$ 1 \leq |S| \leq 10^6 $，保证 $ S $ 只包含大小写、字母。

输出描述
若字符串 $ S $ 为回文串，则输出Y，否则输出N。

输入输出样例

示例 1 输入 abcba 输出 Y

示例 2 输入 abcbb 输出 N

✅ 我的代码（完全保留原始写法）

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;chars[N];intmain(){cin>>s+1;intn=strlen(s+1);intl=1;intr=n;intflag=1;while(l<r){if(s[l]!=s[r]){flag=0;break;}++l;--r;}if(flag)cout<<"Y";elsecout<<"N";return0;}

🔹 题目二：美丽的区间

题目描述
给定一个长度为 $ n $ 的序列 $ a_1, a_2, \ldots, a_n $ 和一个常数 $ S $。

对于一个连续区间，如果它的区间和大于或等于 $ S $，则称它为美丽的区间。
对于一个美丽的区间，如果其区间长度越短，它就越美丽。

请你从序列中找出最美丽的区间。

输入描述
第一行包含两个整数 $ n, S $，其含义如题所述。
接下来一行包含 $ n $ 个整数，分别表示 $ a_1, a_2, \ldots, a_n $。

约束：$ 10 \leq N \leq 10^5，，，1 \leq a_i \leq 10^4，，，1 \leq S \leq 10^8 $。

输出描述
输出共一行，包含一个整数，表示最美丽的区间的长度。
若不存在任何美丽的区间，则输出 0。

输入输出样例

示例 1 输入 5 6 1 2 3 4 5 输出 2

✅ 我的代码（完全保留原始写法）

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;inta[N];intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn,s;cin>>n>>s;intsum=0;intans=n+1;for(inti=1;i<=n;++i)cin>>a[i];for(intl=1,r=0;l<=n;++l){while(l>r||(r+1<=n&&sum<s)){r++;sum+=a[r];}if(sum>=s){ans=min(ans,r-l+1);}sum-=a[l];}cout<<(ans>n?0:ans);return0;}

🔹 题目三：挑选子串

题目描述
有 $ n $ 个数，和一个整数 $ m $。

现要从这 $ n $ 个数选出一个连续子串，要求这个子串里面至少有 $ k $ 个数要大于等于 $ m $。

问一共能选出多少个子串（显然子串长度要大于等于 $ k $）。

输入描述
输入第一行是 3 个整数 $ n, m, k $。
输入第二行是 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $，表示序列。

约束：$ 2 \leq n \leq 2000，，，1 \leq k \leq \frac{n}{2}，，，1 \leq m, a_i \leq 10^9 $。

输出描述
输出一个整数表示答案。

输入输出样例

示例 输入 7 4 2 4 2 7 6 5 1 输出 18

运行限制

最大运行时间：1s
最大运行内存：256M

✅ 我的代码（完全保留原始写法）

#include<bits/stdc++.h>usingnamespacestd;constintN=2e3+5;inta[N];intmain(){intn,m,k;cin>>n>>m>>k;for(inti=1;i<=n;++i)cin>>a[i];intans=0;for(intl=1,r=0,cnt=0;l<=n;++l){while(l>r||(r<n-1&&cnt<k)){cnt+=(a[++r]>=m);}if(cnt>=k)ans+=n-r+1;cnt-=(a[l]>=m);}cout<<ans<<endl;return0;}