LeetCode LCR180文件组合

滑动窗口算法：寻找连续文件编号组合

问题描述

在文件传输过程中，待传输的文件被切分成多个部分，每个部分的文件编号为一个正整数（至少有两个文件）。传输的要求是：找到所有连续文件编号的组合，使得这些文件编号的总和等于接收方指定的数字 target。返回的结果需要满足以下规则：

每种组合按照文件编号升序排列。
不同组合按照第一个文件编号升序排列。

例如，当 target = 15 时，符合条件的组合有：

[1, 2, 3, 4, 5]（因为 1 + 2 + 3 + 4 + 5 = 15）
[4, 5, 6]（因为 4 + 5 + 6 = 15）
[7, 8]（因为 7 + 8 = 15）

解题思路

这个问题可以看作是一个典型的滑动窗口问题。我们需要找到所有连续的文件编号组合，使得它们的总和等于 target。滑动窗口算法非常适合解决这种连续子数组或子序列的问题。

滑动窗口的核心思想

滑动窗口算法通过维护一个窗口（通常是一个连续的子数组或子序列），在满足一定条件的情况下，动态调整窗口的起始和结束位置。具体到这个问题：

初始化窗口：使用两个指针 left 和 right，分别指向窗口的起始和结束位置。
计算窗口内的总和：
- 如果总和小于 target，则扩大窗口（移动 right 指针）。
- 如果总和大于 target，则缩小窗口（移动 left 指针）。
- 如果总和等于 target，则记录当前的组合，并继续寻找下一个可能的组合。
终止条件：当 left 指针超过 target / 2 时，停止搜索（因为至少需要两个文件编号）。

为什么滑动窗口适合这个问题？

连续子序列：文件编号是连续的，滑动窗口天然适合处理连续子序列的问题。
高效性：滑动窗口的时间复杂度为 O(n)，远优于暴力枚举的 O(n²)。
简洁性：代码实现简单，逻辑清晰。

代码实现

#include <stdio.h>
#include <stdlib.h>int** fileCombination(int target, int* returnSize, int** returnColumnSizes) {// 初始化结果数组int** result = (int**)malloc(1000 * sizeof(int*));*returnColumnSizes = (int*)malloc(1000 * sizeof(int));*returnSize = 0;int left = 1, right = 1; // 窗口的起始和结束位置int sum = 0; // 窗口内文件编号的总和while (left <= target / 2) {if (sum < target) {// 总和小于 target，扩大窗口sum += right;right++;} else if (sum > target) {// 总和大于 target，缩小窗口sum -= left;left++;} else {// 找到符合条件的组合int* combination = (int*)malloc((right - left) * sizeof(int));for (int i = left; i < right; i++) {combination[i - left] = i;}(*returnColumnSizes)[*returnSize] = right - left;result[*returnSize] = combination;(*returnSize)++;// 移动左指针，继续寻找下一个组合sum -= left;left++;}}return result;
}int main() {int target = 15;int returnSize;int* returnColumnSizes;int** result = fileCombination(target, &returnSize, &returnColumnSizes);// 输出结果for (int i = 0; i < returnSize; i++) {for (int j = 0; j < returnColumnSizes[i]; j++) {printf("%d ", result[i][j]);}printf("\n");free(result[i]); // 释放每个组合的内存}// 释放结果数组和列大小数组free(result);free(returnColumnSizes);return 0;
}