剑指offer--面试题57 - II. 和为s的连续正数序列

淩亂°似流年 2023-02-18 11:58 78阅读 0赞

## 题目描述 ##

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

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

**示例 1：**

输入：target = 9  
输出：\[\[2,3,4\],\[4,5\]\]

**示例 2：**

输入：target = 15  
输出：\[\[1,2,3,4,5\],\[4,5,6\],\[7,8\]\]

**限制：**

1 <= target <= 10^5

## 思路:滑动窗口，双指针法 ##

和[和为s的两个数][s]这个题类似

**和为s的两个数**：利用双指针解决  
**和为s的连续正数序列**：滑动窗口

窗口长这样  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70]

## 解决方法 ##

class Solution {
        
        public int[][] findContinuousSequence(int target) {
        
            int i=1, j=1, sum=0;
            List<int[]> res = new ArrayList<>();
            while(i <= target/2){
        
                if(sum < target){
          //sum比target小，窗口右边界右移
                    sum += j;
                    j++;
                }else if(target < sum){
          //sum比target大，窗口左边右移
                    sum -= i;
                    i++;
                }else{
           //sum等于target，保存窗口的所有值
                    int[] arr = new int[j-i];  
                    for(int k=i; k<j; k++){
        
                        arr[k-i] = k;
                    }
                    res.add(arr);  //保存一次窗口的值
                    //重点：保存完，窗口左边界向右移动，再次查找
                    sum -= i; 
                    i++;
                }
            }
            return res.toArray(new int[res.size()][]); //通过 return res.toArray(new int[res.size()][]);转成二维数组
        }
    }

[s]: https://blog.csdn.net/weixin_43730508/article/details/106789341
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617191329809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMDUwOA==,size_16,color_FFFFFF,t_70