1. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

  1. 示例 1：
  3. 输入：target = 9
  4. 输出：[[2,3,4],[4,5]]
  5. 示例 2：
  7. 输入：target = 15
  8. 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
  11. 限制：
  12. 1 <= target <= 10^5

思路：

  • 暴力枚举

    class Solution {
  public int[][] findContinuousSequence(int target) {
      int mid = (target+1)/2;
      int total = 0;
      int count = 0;
      int index = 0;
      // int[][] res = new int[100][];
      List<int[]> res = new ArrayList<>();
      for(int i=1;i<=mid;i++){
          for(int k=1;k<=i;k++){
              total = 0;
              for(int j=i;j>=k;j--){
                  total +=j;
              }
              if(total == target){
                  index = 0;
                  int[] arr = new int[i-k+1];
                  for(int a = k;a<=i;a++){
                      arr[index++] = a;
                  }
                  res.add(arr);
                  count++;
              }
          }

      }
      return res.toArray(new int[res.size()][]);
  }
}

    优秀解法：双指针滑动窗口

  • 前提：

    • 双指针保证左闭右开
    • 左指针从开0开始，右指针从1开始
  • 策略：
    • 如果窗口的数<target，右指针后移
    • 如果窗口的数>target，左指针后移
  • 循环结束的标志：
    • 右指针超过（target+1）/2的位置
      class Solution {
public int[][] findContinuousSequence(int target) {
   int left = 1;
   int right = 2;
   int mid = (target+1)/2;
   int total = left;
   List<int[]> res = new ArrayList<>();
   while(right<=mid+1){
       if(total==target){
           int[] arr = new int[right-left];
           for(int i=left;i<right;i++){
               arr[i-left] = i;
           }
           res.add(arr);
           total-=left;
           left++;
       }else if(total>target){
           total-=left;
           left++;
       }else {
           total += right;
           right++;
       }
   }
   return res.toArray(new int[res.size()][]);
}
}