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

• 2021 年 10 月 30 日
• 笔记
• 双指针, 数组, 滑动窗口, 算法

题目

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

思路1（双指针/滑动窗口）

• 所谓滑动窗口，就是需要我们从一个序列中找到某些连续的子序列，我们可以使用两个for循环来遍历查找，但是未免效率太低了。因此我们可以用一个窗口，从左到右只需要遍历一次，然后每次判断当前窗口是否满足条件，不满足就扩大窗口或者缩小窗口，当滑动窗口从左边滑动到了右边，就可以得到最优解了。
• 滑动窗口的左边界和右边界都只能向右移动，因此只遍历一遍数组，从而时间复杂度是\(O(N)\)
• 该题要求是待遍历的序列是从1～target可构建一个滑动窗口从左向右滑动，窗口边界为left、right，初始的时候left=left=1
• 窗口的有效范围就是窗口左边界要小于右边界，即left < right
• 每次循环中，将窗口里面的数字的总和sum与target进行比较：
  • 如果target > sum，说明窗口大了，需要将当前left从sum中删除，同时left右移一步
  • 如果target < sum，说明窗口笑了，需要将当前right从sum中删除，同时right右移一步
  • 如果target = sum，则找到一段序列等于target，记录下该子序列，同时left向右移动一步
• 我们以target=9为例，求解流程如下：
  • 

代码

class Solution {
    public int[][] findContinuousSequence(int target) {
        int sum = 3;
        int left = 1;
        int right = 2;
        List<int[]> res = new ArrayList<>();

        while (left < right) {
            // 当前窗口符合要求
            if (sum == target) {
                // 加入到结果集中
                int[] temp = new int[right - left + 1];
                for (int i = left; i <= right; i++) {
                    temp[i-left] = i;
                }
                res.add(temp);
            }

            // 窗口过大，要缩小窗口
            if (sum >= target) {
                // 这里要先将left从sum中减去，然后再右移一位，因为当前left是即将被移出窗口，这样才能保证left是窗口的左边界
                sum -= left;
                left++;
            } else if (sum < target) {
                // 这里要先将right自增，然后将right加入到sum中，因为先自增才能获取到窗口后一位的元素，然后加入到窗口中，保证了right是窗口的右边界
                right++;
                sum += right;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，其中N=target
• 空间复杂度：\(O(1)\)