题目链接: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 之前遍历,就可以起到 “剪枝” 的作用了。但这道题如果数组中有负数,就得采用前缀和了。