如何实现数组多起始点连续子序列求和及重复和值查找？

核心逻辑调整 #

原来的代码仅处理第一个起始点，要覆盖所有起始点，只需在外层添加起始索引循环：

• 遍历数组每个元素作为子序列起始位置i（i的上限为数组长度-2，保证至少能包含1个后续元素，子序列长度从2开始）
• 对每个i，从i+1开始逐步累加后续元素，计算i到当前位置j的连续子序列和
• 用统计容器记录每个和的出现次数，最后筛选出出现次数≥2的和

修改后的C语言代码示例 #

以你提供的示例数组{1,5,2,4,2,2,2}为例：

#include <stdio.h>

#define MAX_SUM 200  // 根据数组元素大小调整，确保能容纳所有可能的子序列和

int main() {
    int arr[] = {1,5,2,4,2,2,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum_count[MAX_SUM] = {0};  // 初始化统计数组，记录每个和的出现次数
    int i, j, current_sum;

    // 遍历每个起始点
    for (i = 0; i < n - 1; i++) {
        current_sum = arr[i];
        // 从i的下一个元素开始，逐步扩展子序列长度
        for (j = i + 1; j < n; j++) {
            current_sum += arr[j];  // 得到i到j的连续子序列和
            if (current_sum < MAX_SUM) {
                sum_count[current_sum]++;
            }
        }
    }

    // 输出所有重复的和值
    printf("重复的子序列和：\n");
    for (int s = 0; s < MAX_SUM; s++) {
        if (sum_count[s] >= 2) {
            printf("%d\n", s);
        }
    }

    return 0;
}

代码说明 #

1. 起始点遍历：for (i = 0; i < n - 1; i++) 确保每个元素都能作为起始点，且子序列长度至少为2
2. 累加计算：对每个起始点i，current_sum从arr[i]开始，每次累加arr[j]得到i到j的连续和（子序列长度从2逐步增加到n-i）
3. 重复项筛选：通过sum_count数组统计每个和的出现次数，最后遍历数组找出出现≥2次的和，即为重复项

示例验证 #

针对数组1 5 2 4 2 2 2：

• 起始点i=0的子序列和：6、8、12、14、16、18
• 起始点i=2的子序列和：6、8、10、12
• 最终会输出6、8、12这三个重复的和值

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