连续整数和为N的倍数求解：C++代码正确但运行过慢优化求助

1. 核心算法效率优化 #

你当前使用的三重循环枚举所有子数组求和的方案时间复杂度为O(n³)，面对1e5量级的数据完全无法满足性能要求，最优解法采用前缀和余数匹配思路，时间复杂度可降到O(n)：

• 核心原理：定义前缀和prefix[i]为数组前i个元素的和（prefix[0] = 0，prefix[1] = array[0]，prefix[2] = array[0]+array[1]以此类推），如果prefix[a] % n == prefix[b] % n，则子数组[a, b-1]的和一定是n的倍数。
• 鸽巢原理保证：总共n+1个前缀和，模n的余数最多只有n种可能，因此必然存在至少一组符合要求的子数组，不需要全量枚举。
• 实现方式：用一个长度为n的数组存储每个余数第一次出现的下标，遍历计算前缀和余数的过程中只要碰到已经出现过的余数，就可以直接得到结果，立刻终止程序。

2. 整数溢出问题解决 #

不需要计算完整的前缀和，每次计算的时候直接对n取模即可：

• 根据模运算性质：(a + b) % n = ((a % n) + (b % n)) % n，每次只需要保留前缀和模n的结果，数值范围永远在[0, n-1]（如果要兼容负数可以调整为[-(n-1), n-1]，加n再取模即可转成正余数），用标准int类型完全不会溢出，不需要使用unsigned int。

优化后代码 #

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    // 加速输入输出，适配大数据量场景
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases = 0, n = 0;
    const int arraySize = 100000;
    int array[arraySize];
    
    ofstream outFile("output.txt");
    ifstream inFile("input.txt");
    
    inFile >> testCases;
    
    while(testCases--)
    {
        inFile >> n;
        for(int a = 0; a < n; a++)
            inFile >> array[a];
        
        vector<int> rem_pos(n, -1); // 存储余数第一次出现的下标，初始为-1表示未出现
        rem_pos[0] = 0; // prefix[0] = 0，余数为0，对应下标0
        int current_rem = 0;
        bool found = false;
        
        for(int i = 0; i < n && !found; i++)
        {
            current_rem = (current_rem + array[i]) % n;
            // 处理负余数，保证余数非负
            if(current_rem < 0)
                current_rem += n;
            
            if(rem_pos[current_rem] != -1)
            {
                // 子数组范围是[rem_pos[current_rem], i]
                outFile << rem_pos[current_rem] << ' ' << i << '\n';
                found = true;
            }
            else
            {
                rem_pos[current_rem] = i + 1;
            }
        }
    }
    
    outFile.close();
    inFile.close();
    
    return 0;
}

内容的提问来源于stack exchange，提问作者Mark Keasal