如何从含重复元素的7个已排序整数数组中找出并存储5连数子数组？

给定一个包含7个已排序整数（允许重复）的数组，我们需要找出所有由连续递增1的5个数字组成的子数组（子数组元素需保持原数组的排序顺序，且元素值构成连续序列）。以示例数组{1, 2, 3, 4, 4, 5, 6}为例，最终能得到4个符合要求的子数组，原因是重复的4为两个连续序列（1-5、2-6）各提供了两种组合可能。

核心思路 #

1. 频率统计：先统计数组中每个数字的出现次数，因为数组已排序，可快速确定数字范围，用数组存储频率更高效。
2. 连续序列校验：遍历所有可能的连续5数起始值x，检查x、x+1、x+2、x+3、x+4是否都在原数组中存在（频率>0）。
3. 计算组合数：对于每个有效的连续序列，各数字频率的乘积就是该序列能生成的子数组数量。
4. 生成子数组：通过多重循环枚举每个数字的重复选择，生成所有符合要求的子数组并存储。

C语言实现代码 #

#include <stdio.h>
#include <stdlib.h>

int main() {
    int bigArray[7] = {1, 2, 3, 4, 4, 5, 6};
    int arrSize = 7;
    int minVal = bigArray[0];
    int maxVal = bigArray[arrSize - 1];
    
    // 统计每个数字的出现频率
    int freqSize = maxVal - minVal + 1;
    int* freq = (int*)calloc(freqSize, sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        freq[bigArray[i] - minVal]++;
    }
    
    // 先计算符合要求的子数组总数，用于分配内存
    int totalStraights = 0;
    for (int x = minVal; x <= maxVal - 4; x++) {
        int isValid = 1;
        int comboCount = 1;
        for (int i = 0; i < 5; i++) {
            int currentNum = x + i;
            int freqIndex = currentNum - minVal;
            if (freq[freqIndex] == 0) {
                isValid = 0;
                break;
            }
            comboCount *= freq[freqIndex];
        }
        if (isValid) {
            totalStraights += comboCount;
        }
    }
    
    // 分配存储子数组的二维内存
    int** arrayOfStraights = (int**)malloc(totalStraights * sizeof(int*));
    for (int i = 0; i < totalStraights; i++) {
        arrayOfStraights[i] = (int*)malloc(5 * sizeof(int));
    }
    
    // 生成所有符合要求的子数组
    int currentPos = 0;
    for (int x = minVal; x <= maxVal - 4; x++) {
        int nums[5];
        int numFreqs[5];
        int isValid = 1;
        
        // 验证当前连续序列是否有效，并记录数字和对应频率
        for (int i = 0; i < 5; i++) {
            int currentNum = x + i;
            int freqIndex = currentNum - minVal;
            if (freq[freqIndex] == 0) {
                isValid = 0;
                break;
            }
            nums[i] = currentNum;
            numFreqs[i] = freq[freqIndex];
        }
        if (!isValid) continue;
        
        // 枚举所有组合，生成子数组
        for (int a = 0; a < numFreqs[0]; a++) {
            for (int b = 0; b < numFreqs[1]; b++) {
                for (int c = 0; c < numFreqs[2]; c++) {
                    for (int d = 0; d < numFreqs[3]; d++) {
                        for (int e = 0; e < numFreqs[4]; e++) {
                            arrayOfStraights[currentPos][0] = nums[0];
                            arrayOfStraights[currentPos][1] = nums[1];
                            arrayOfStraights[currentPos][2] = nums[2];
                            arrayOfStraights[currentPos][3] = nums[3];
                            arrayOfStraights[currentPos][4] = nums[4];
                            currentPos++;
                        }
                    }
                }
            }
        }
    }
    
    // 输出结果
    printf("共生成%d个符合要求的子数组：\n", totalStraights);
    for (int i = 0; i < totalStraights; i++) {
        printf("{");
        for (int j = 0; j < 5; j++) {
            printf("%d", arrayOfStraights[i][j]);
            if (j != 4) printf(", ");
        }
        printf("}\n");
    }
    
    // 释放动态分配的内存
    for (int i = 0; i < totalStraights; i++) {
        free(arrayOfStraights[i]);
    }
    free(arrayOfStraights);
    free(freq);
    
    return 0;
}

代码说明 #

• 频率统计：利用已排序数组的首尾元素确定数字范围，用calloc初始化频率数组，遍历原数组统计每个数字的出现次数。
• 序列校验：遍历每个可能的起始值x，检查连续5个数是否都存在，若存在则计算该序列的组合数。
• 子数组生成：通过5层循环枚举每个数字的重复选择，生成所有可能的子数组，保证每个子数组都符合连续数字的要求。
• 内存管理：先计算总数再分配内存，避免内存浪费，使用完成后及时释放动态分配的内存，防止内存泄漏。

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