从零学算法（LCR 180）

文件组合.待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。
注意，返回时需遵循以下规则：
每种组合按照文件编号 升序 排列；
不同组合按照第一个文件编号 升序 排列。
示例 1：
输入：target = 12
输出：[[3, 4, 5]]
解释：在上述示例中，存在一个连续正整数序列的和为 12，为 [3, 4, 5]。
示例 2：
输入：target = 18
输出：[[3,4,5,6],[5,6,7]]
解释：在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。

• 他人解法1：连续整数和等于某个数，我们知道连续和 i~j 的公式为平均值(首尾相加除以2)乘以元素个数(j-i+1)
  
• target 是确定的，那么只要我们让 i 从 1 开始往后找就能找到一堆 j，只要 j 为整数就说明我们找到了一种组合，直到 i >= j 我们就停止寻找，把公式经过移项能得到关于 j 的一元二次方程，然后求解就能得到 j 的公式
  
• j 不可能为负数，所以只要那个 (-1 + 根号xx) / 2 就可以了

•   public int[][] fileCombination(int target) {
        int i = 1;
        double j = 2.0;
        List<int[]> list = new ArrayList<>();
        while(i < j){
            j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
            // j 为整数
            if (j == (int)j){
                int[] ans = new int[(int)j-i+1];
                for(int k=i;k<=j;k++){
                    ans[k-i] = k;
                }
                list.add(ans);
            }
            i++;
        }
        return list.toArray(new int[0][]);
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

• 他人题解2：滑动窗口，我们初始化双指针 i，j 为 1, 2，此时连续和 s 为 3，我们比较 s 和 target，如果小了，那就得补上，我们就把 j 往后移成 3，s 更新为 1+2+3=6，而如果大了，那就得减少和，就把 i 往右移去掉一个最小的值，即 s 更新为 2，i 更新为 2。比如 target 为 9，我们一开始只有 3，就需要补充更多数字，右边界 j 右移则相当于扩充连续和范围，从 1~2 扩充为 1~3，此时和 s 为 6；下一轮比较发现还是不够，继续扩充为 1~4 ，s 为 10 了；再比较，这次太大了，我们右移 i 则相当于缩小连续和范围，从 1~4 缩小至 2~4，此时和为 9，那么我们就把此时的 2~4 作为一种组合存入结果列表，等于的时候，你扩充或缩小都无所谓，反正 i 和 j 都是一步一步移动，移动一次判断一次，所以不会遗漏某种情况。不断移动的过程中，由于后来 j 越来越大，所以 i 怎么右移（缩小范围）最后连续和 s 都大于 target，就会使得 i == j，此时退出循环即可，而比如 i~j 为 4~5 时，此时是一种可行组合， s == target，其实缩到这种只有两个数的地步，不可能再有其他组合了，虽然可以选择扩充和缩小，不过选择缩小就能直接结束循环了，扩充还得多判断几轮无意义的循环，所以我们在 s == target 时选择缩小

•   public int[][] fileCombination(int target) {
        int i = 1,j = 2, s = 3;
        List<int[]> list = new ArrayList<>();
        while(i < j){
            if (s == target){
                int[] ans = new int[(int)j-i+1];
                for(int k=i;k<=j;k++){
                    ans[k-i] = k;
                }
                list.add(ans);
            }
            if(s >= target){
            	// 比如原本 i，j 为 2,4，s = 2+3+4 = 9，此时减掉 i 就相当于 s 成了 3+4 = 7
                s-=i;
                i++;
            }else{
                j++;
                s+=j;
            }
        }
        return list.toArray(new int[0][]);
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22