面试题57 - II. 和为s的连续正数序列-阿里云开发者社区

面试题57 - II. 和为s的连续正数序列

2022-05-24 72

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 面试题57 - II. 和为s的连续正数序列

输入一个正整数 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

题解

按照纯数学平均数的想法来做的，代码可能写的比较啰嗦。

设最多能有n个数加起来能等于target, 则n >= 2
以n >= 2为while循环条件，找出这n个数字的平均数，注意Python3使用//进行除法会得到向下取整的整数
这个是重点，由于序列每个数字都必须为正整数，所以n个数字中最小的数字必须大于或等于1.

根据第三点，可以轻易得出一个公式：

当n为偶数时：平均数 - n // 2 + 1 >= 1

举个例子，target=9, n=4的时候，平均数为2，所以4个数字必须是围绕2组成，并且大小均匀分布，由于n=4，导致数组有2种情况, 分别为: [0, 1, 2, 3]和[1, 2, 3, 4]，当第二种情况的最小数字都小于1的时候，第一种情况必定也会小于1，所以此时的判断公式为平均数 - n // 2 + 1 >= 1

当n为奇数时：平均数 - n // 2 >= 1

此时比较简单，中位数就是平均数，所以左右均匀分配，只需要平均数 - n // 2 >= 1即可。

最后是n = 2的时候，由于数字不能重复，只要n是偶数，那么绝对不可能有2个一样的数字组成这个target。如果n是奇数，则mid为向下取余的数字，必有奇数target = mid+(mid+1)

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # 最终结果数组
        result = []
        # 初始化target
        n = target
        while n > 2:
            mid = target // n
            # 判断n是否为偶数
            if n % 2 == 0:
                if mid - n // 2 + 1 < 1:
                    # 如果此序列的最小值都小于1，则n-- 循环继续
                    n -= 1
                    continue
                # 满足第一种情况
                if sum(range(mid - n // 2, mid + n // 2)) == target:
                    result.append(list(range(mid - n // 2, mid + n // 2)))
                # 满足第二种情况
                elif sum(range(mid - n // 2 + 1, mid + n // 2 + 1)) == target:
                    result.append(list(range(mid - n // 2 + 1, mid + n // 2 + 1)))
            else:
                # 奇数时候，最小值小于1则继续循环
                if mid - n // 2 < 1:
                    n -= 1
                    continue
                if sum(range(mid - n // 2, mid + n // 2 + 1)) == target:
                    result.append(list(range(mid - n // 2, mid + n // 2 + 1)))
            n -= 1
        # 由于n >= 2
        if target % 2 != 0:
            mid = target // 2
            result.append([mid, mid + 1])
        return result