从零学算法（LCR 180）-Toy模板网

这篇具有很好参考价值的文章主要介绍了从零学算法（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]。文章来源地址https://www.toymoban.com/news/detail-726985.html

他人解法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][]);
  }

他人题解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][]);
  }