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

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

  • 标签:数学、双指针、枚举
  • 难度:简单

题目大意 #

描述:给定一个正整数 target

要求:输出所有和为 target 的连续正整数序列(至少含有两个数)。序列中的数字由小到大排列,不同序列按照首个数字从小到大排列。

说明

  • $1 \le target \le 10^5$。

示例

1
2
输入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:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 = 1right = 2
  • 计算 sum = (left + right) * (right - left + 1) // 2
  • 如果 sum == target,时,将其加入答案数组中。
  • 如果 sum < target 时,说明需要扩大窗口,则 right += 1
  • 如果 sum > target 时,说明需要缩小窗口,则 left += 1
  • 直到 left >= right 时停止,返回答案数组。

思路 2:滑动窗口代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        left, right = 1, 2
        res = []
        while left < right:
            sum = (left + right) * (right - left + 1) // 2
            if sum == target:
                arr = []
                for i in range(0, right - left + 1):
                    arr.append(i + left)
                res.append(arr)
                left += 1
            elif sum < target:
                right += 1
            else:
                left += 1
        return res
本站总访问量  次  |  您是本站第  位访问者