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

约 4 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节跳动 美团 腾讯 华为 拼多多 剑指 Offer 剑指 Offer（第 2 版）
标签
数学 双指针 子数组问题 枚举
目录

题目描述

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

image-20241107212159667

题意分析

给定一个正整数 target，要在正整数序列里找出所有连续的一段，使这段数之和恰好等于 target，并且每段至少包含两个数。答案按每段的起始元素从小到大给出。

约束信号有三个。第一，参与组合的数全是正整数，没有 0 也没有负数；第二，只能取连续的一段，不能跳着挑；第三，长度至少为 2，所以 target 自己单独成段不算答案。

边界要先想清楚。最短的一段是两个相邻整数；最小的可能起点是 1；起点也不可能太大，因为从 k 开始的两项和已经是 2k + 1，一旦 2k + 1 > target 就再也凑不出任何合法段；target 取 1 或 2 时无解，应当返回空数组。

解法：滑动窗口

核心思路

序列由连续正整数组成，窗口 [left, right] 的和具有单调性：右端点右移，和一定增大；左端点右移，和一定减小。这正是滑动窗口成立的条件。

维护窗口和 sum。当 sum < target 时，当前窗口太小，只能右移 right 扩大；当 sum >= target 时，先在相等时记录答案，再右移 left 缩小。两个指针都不回退，因此不会漏掉任何连续区间。

窗口至少要包含两个正整数，所以初始化为 [1,2]，并以 left < right 作为循环条件。相等后必须继续收缩，否则会停在同一个答案上死循环。

解题步骤

  1. 初始化 left = 1、right = 2、sum = 3。
  2. 当 left < right 时比较 sum 与 target。
  3. 若相等，生成 [left, right] 对应的连续序列并加入答案。
  4. 若 sum >= target，从和中减去 left，再令 left++。
  5. 若 sum < target，先令 right++，再把新的 right 加入窗口和。

例如 target = 9：窗口依次经过 [1,4]、[2,4]，得到 2+3+4=9；继续收缩和扩张后还能得到 4+5=9。

代码实现

import java.util.ArrayList;
import java.util.List;

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

        while (left < right) {
            if (sum == target) {
                int[] sequence = new int[right - left + 1];
                for (int i = 0; i < sequence.length; i++) {
                    sequence[i] = left + i;
                }
                result.add(sequence);
            }

            if (sum >= target) {
                sum -= left;
                left++;
            } else {
                right++;
                sum += right;
            }
        }
        return result.toArray(new int[0][]);
    }
}

func findContinuousSequence(target int) [][]int {
	result := make([][]int, 0)
	left, right, sum := 1, 2, 3

	for left < right {
		if sum == target {
			sequence := make([]int, right-left+1)
			for i := range sequence {
				sequence[i] = left + i
			}
			result = append(result, sequence)
		}

		if sum >= target {
			sum -= left
			left++
		} else {
			right++
			sum += right
		}
	}
	return result
}

复杂度分析

  • 时间复杂度：窗口移动为 $O(target)$；构造所有返回序列还需与输出元素总数相同的时间。
  • 空间复杂度：$O(1)$，不计返回结果，只维护三个整数。

关键点总结

  • 正整数保证窗口和随指针移动单调变化，这是滑动窗口的依据。
  • 窗口和小就扩右边，大或相等就缩左边，两个指针永不回退。
  • left < right 明确排除长度为 1 的序列。
  • 命中答案后仍要收缩窗口，才能继续寻找后续解。

易错点总结

  • 命中 target 后只记录不移动，会造成死循环。
  • 移动指针时忘记同步更新 sum，窗口边界与窗口和会失配。
  • 循环条件写成 left <= right 会把单个 target 当成合法序列。
  • 本方法依赖元素全为正数；若允许负数，窗口和不再单调，不能照搬。

相似题目

题目 难度 考察点
209. 长度最小的子数组 中等 变长滑动窗口求最短
829. 连续整数求和 困难 连续序列的因数分解
剑指 Offer 57. 和为s的两个数字 简单 有序数组对撞双指针