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

解题的笔记

news 2026/7/6 12:47:18

最近在解决一个~~看似简单的~~算法问题时，我遇到了一个令人困扰的Runtime Error（RE）。经过仔细调试，发现问题的根源在于对数据范围的忽视和算法选择不当。今天我想分享这次经历，希望能帮助到遇到类似问题的朋友们。

问题描述

题目要求：给定一个长度为n的数组和整数m，找出所有长度为m的连续子数组的最小和。

数据范围：

对于100%的数据，保证 0≤m≤n≤3×10³
数组元素范围：1≤aᵢ≤100

初版代码与RE

我最开始写的代码是这样的：

#include<bits/stdc++.h> using namespace std; int main() { int n,m,a[100]; // 问题所在！ long long sum=0; cin>>n>>m; if(m>n||n<0||m<=0) { cout<<0; return 0; } for(int i=0;i<n;i++) { cin>>a[i]; // 当n>100时，这里会数组越界！ } long long min=INT_MAX; for(int i=0;i<=n-m;i++) { sum=0; for(int j=i;j<i+m;j++) { sum+=a[j]; } if(sum<min) min=sum; } cout<<min; return 0; }

问题分析

1. 数组大小不足（致命错误）

问题：数组a的大小只有100，但题目中n最大可达3000。

后果：当输入n>100时，cin>>a[i]会访问a[100]到a[2999]，这些内存位置不属于数组a，导致数组越界，引发Runtime Error。

教训：永远要根据数据范围分配足够的数组空间。

2. 数据类型选择不当

问题：使用int min=INT_MAX但sum是long long。

潜在风险：如果sum的值超过INT_MAX（约21亿），比较和赋值可能出错。虽然题目中最大和=3000×100=300,000 < INT_MAX，不会出错，但这是不好的编程习惯。

教训：保持数据类型一致性，对于和值使用long long更安全。

3. 算法效率低下

问题：使用双重循环，时间复杂度O(n×m)。

计算：最坏情况n=3000, m=3000，需要约9百万次加法操作。虽然现代计算机能处理，但存在优化空间。

解决方案

修正版1：修复数组大小

int a[3001]; // 根据数据范围调整大小

修正版2：完整正确的代码

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); // 输入输出优化 int n, m, a[3001]; // 足够的空间 cin >> n >> m; // 处理边界情况 if(m == 0) { cout << 0 << endl; return 0; } if(m > n || m <= 0) { cout << 0 << endl; return 0; } for(int i = 0; i < n; i++) { cin >> a[i]; } long long min_sum = LLONG_MAX; // 使用正确的最大值 for(int i = 0; i <= n - m; i++) { long long sum = 0; for(int j = i; j < i + m; j++) { sum += a[j]; } if(sum < min_sum) { min_sum = sum; } } cout << min_sum << endl; return 0; }

优化版：滑动窗口算法

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, a[3001]; cin >> n >> m; if(m == 0) { cout << 0 << endl; return 0; } for(int i = 0; i < n; i++) { cin >> a[i]; } // 滑动窗口算法 long long window_sum = 0; for(int i = 0; i < m; i++) { window_sum += a[i]; } long long min_sum = window_sum; // 滑动窗口，每次更新只需两次操作 for(int i = m; i < n; i++) { window_sum = window_sum - a[i - m] + a[i]; if(window_sum < min_sum) { min_sum = window_sum; } } cout << min_sum << endl; return 0; }