如何在O(n)时间复杂度下计算列表忽略重复元素的累计和

无界RAM模型下不需要复杂数据结构，直接利用内存随机访问O(1)的特性即可实现，核心思路是用标记位记录已经出现过的非负整数：

• 初始化全局累计和sum = 0，以及一个初始全为false的布尔标记数组exist（无界RAM下无需预分配固定大小，直接用输入数值作为下标访问）
• 遍历输入列表的每个元素：
  • 若当前元素对应的exist[num]为false：将num加到sum中，同时把exist[num]设为true
  • 若当前元素对应的exist[num]为true：sum保持不变
• 每处理完一个元素就输出当前的sum值

示例验证 #

对应你给出的输入{3,2,3,12,2}，运行流程完全匹配预期输出：

1. 处理3：未标记，sum=3 → 输出3
2. 处理2：未标记，sum=5 → 输出5
3. 处理3：已标记，sum不变 → 输出5
4. 处理12：未标记，sum=17 → 输出17
5. 处理2：已标记，sum不变 → 输出17

伪代码 #

sum = 0
// exist数组默认所有位置初始值为false
for num in input:
    if not exist[num]:
        sum += num
        exist[num] = true
    print sum

复杂度说明 #

• 时间复杂度：每个元素仅执行1次查询、最多1次写入和1次加法操作，所有操作都是O(1)，总复杂度严格O(n)
• 空间复杂度：仅和输入中不同元素的最大值有关，无界RAM模型下无内存限制，完全满足要求

内容的提问来源于stack exchange，提问作者Skill HHY