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

杨世超 · 杨世超 · commit 860f344b4e85 · 2022-04-06T20:27:30.000+08:00
diff --git a/Solutions/剑指 Offer 57 - II. 和为s的连续正数序列.md b/Solutions/剑指 Offer 57 - II. 和为s的连续正数序列.md
@@ -5,13 +5,63 @@
 
 ## 题目大意
 
-给定一个正整数 `target`。
+**描述**：给定一个正整数 `target`。
 
-要求：输出所有和为 `target` 的连续正整数序列（至少含有两个数）。序列中的数字由小到大排列，不同序列按照首个数字从小到大排列。
+**要求**：输出所有和为 `target` 的连续正整数序列（至少含有两个数）。序列中的数字由小到大排列，不同序列按照首个数字从小到大排列。
+
+**说明**：
+
+- $1 \le target \le 10^5$。
+
+**示例**：
+
+```Python
+输入	target = 9
+输出	[[2,3,4],[4,5]]
+```
 
 ## 解题思路
 
-滑动窗口求解。具体做法如下：
+### 思路 1：枚举算法
+
+连续正整数序列中元素的最小值大于等于 `1`，而最大值不会超过 `target`。所以我们可以枚举可行的区间，并计算出区间和，将其与 `target` 进行比较，如果相等则将对应的区间元素加入答案数组中，最终返回答案数组。
+
+因为题目要求至少含有两个数，则序列开始元素不会超过 `target` 的一半，所以序列开始元素可以从 `1` 开始，枚举到 `target // 2` 即可。
+
+具体步骤如下：
+
+- 使用列表变量 `res` 作为答案数组。
+- 使用一重循环 `i`，用于枚举序列开始位置，枚举范围为 `[1, target // 2]`。
+- 使用变量 `cur_sum` 维护当前区间的区间和，`cur_sum` 初始为 `0`。
+- 使用第 `2` 重循环 `j`，用于枚举序列的结束位置，枚举范围为 `[i, target - 1]`，并累积计算当前区间的区间和，即 `cur_sum += j`。
+  - 如果当前区间的区间和大于 `target`，则跳出循环。
+  - 如果当前区间的区间和等于 `target`，则将区间上的元素保存为列表，并添加到答案数组中，然后跳出第 `2` 重循环。
+- 遍历完返回答案数组。
+
+### 思路 1：代码
+
+```Python
+class Solution:
+    def findContinuousSequence(self, target: int) -> List[List[int]]:
+        res = []
+        for i in range(1, target // 2 + 1):
+            cur_sum = 0
+            for j in range(i, target):
+                cur_sum += j
+                if cur_sum > target:
+                    break
+                if cur_sum == target:
+                    cur_res = []
+                    for k in range(i, j + 1):
+                        cur_res.append(k)
+                    res.append(cur_res)
+                    break
+        return res
+```
+
+### 思路 2：滑动窗口
+
+具体做法如下：
 
 - 初始化窗口，令 `left = 1`，`right = 2`。
 - 计算 `sum = (left + right) * (right - left + 1) // 2`。
@@ -20,7 +70,7 @@
 - 如果 `sum > target` 时，说明需要缩小窗口，则 `left += 1`。
 - 直到 `left >= right` 时停止，返回答案数组。
 
-## 代码
+### 思路 2：滑动窗口代码
 
 ```Python
 class Solution:
