剑指 Offer 57 - II. 和为s的连续正数序列

妖狐艹你老母 2022-12-19 08:56 154阅读 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

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof][https_leetcode-cn.com_problems_he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof]

# 解题思路 #

使用滑动窗口来解决

*  维护两个指针left = 1和right = 1,滑动窗口内的和记为sum
 *  当left <= target / 2时循环迭代,因为当left > target / 2时,且滑动窗口中的元素大于1个的时候和肯定都大于target
 *  比较滑动窗口的值sum和target的大小
    
     *  sum < target,滑动窗口中的值需要扩大,此时移动右指针,sum += right,right++
     *  sum > target,滑动窗口中的值需要缩小,此时移动左指针,sum -= left,left++
     *  sum == target,满足条件,记录此时滑动窗口中的元素,然后记得移动左指针

# 代码 #

class Solution { 
        public int[][] findContinuousSequence(int target) { 
            // 滑动窗口
            // 创建左右两个指针,左闭右开区间
            int left = 1;
            int right = 1;
            // 滑动窗口的值
            int sum = 0;
            List<int[]> list = new ArrayList<>();
            while (left <= (target >> 1)) { 
                if (sum < target) { 
                    // 滑动窗口中的和需要扩大,右指针右移
                    sum += right;
                    right++;
                } else { 
                    if (sum == target) { 
                        // 满足条件,记录滑动窗口中的值
                        int[] arr = new int[right - left];
                        for (int i = left; i < right; i++) { 
                            arr[i - left] = i;
                        }
                        list.add(arr);
                    }
    
                    // 滑动窗口中的值需要缩小,左指针右移
                    sum -= left;
                    left++;
                }
            }
            return list.toArray(new int[list.size()][]);
        }
    }

# 复杂度 #

*  时间复杂度:O(target),最多移动target / 2次
 *  空间复杂度:O(1),除了答案数组,使用常数级额外空间

[https_leetcode-cn.com_problems_he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof]: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof