题目简介

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

暴力遍历法

最容易想到的就是暴力遍历法，一个个遍历数组，将符合要求的数字添加，直到满足条件 ，数组之和等于target

def findContiniousSequence(target):
    """
    暴力遍历法
    :param target:
    :return:
    """
    ans = []
    for i in range(1, target - 1):
        sum_array = []
        now_num = i
        while sum(sum_array) < target and now_num < target:
            sum_array.append(now_num)
            now_num += 1
            if sum(sum_array) > target:
                break
            elif sum(sum_array) == target:
                ans.append(sum_array.copy())
                break

    return ans

好处：理解容易，思路容易想到
坏处：时间复杂度很大，速度是最慢的

双指针法

利用双指针形成一个窗口
当窗口内总和小于target，就扩张窗口，即向右移动右指针
当窗口内总和大于target，就缩小窗口，就向右移动左指针

def findContiniousSequencev2(target):
    """
    双指针窗口法
    :param target:
    :return:
    """
    i = 1
    j = 2
    ans = []
    while j <= target // 2 + 1:
        cur_sum = sum(list(range(i, j+1)))
        if cur_sum < target:
            # 小于target，扩张窗口，右指针往右
            j += 1
        elif cur_sum > target:
            # 大于target，缩小窗口，左指针往右
            i += 1
        else:
            ans.append(list(range(i, j+1)))
            # 这里改i改j都行
            j += 1

    return ans

求和公式

我们知道等差数列求和是有个通项公式的。
以此为基础我们逐个遍历满足该公式的元素

def findContiniousSequencev3(target):
    # 求根公式遍历法
    """
    设首项为x，尾项为y
    target = (x+y)*(y-x+1)*0.5
    这里把y当常数
    反解出x = (y^2 + y - 2*t + 0.25)^(0.5) + 0.5
    遍历
    :param target:
    :return:
    """
    ans = []
    for y in range(1, target // 2+2):
        x = (y*y + y - 2*target + 0.25)**(1/2) + 0.5
        print(x)
        if type(x) != complex and x - int(x) == 0:
            ans.append(list(range(int(x), y+1)))

    return ans

这里解释一下为什么范围是target // 2 + 1
这是个很简单的想法
比如你target是15
那你肯定只有在0-8的区间去找，因为8 = target / 2
再往后相当于 (target /2) + (target /2 + 1) > target肯定是不满足条件的

间隔法

还是利用等差数列的通项公式，定义y-x = i，i被称为间隔，利用i这个变量消去公式里的y
相当于是在求和公式基础上增加了额外的条件，加快整个遍历过程

def findContiniousSequencev4(target):
    """
    :param target:
    :return:
    """
    i = 1
    ans = []
    while i*(i+1)/2 < target:
        if not (target - i*(i+1)/2) % (i+1):
            x = int((target - i*(i+1)/2) // (i+1))
            ans.append(list(range(x, x+i+1)))

        i += 1
    ans = ans[::-1]
    return ans

最后

以上就是负责果汁最近收集整理的关于LEETCODE 和为s的连续正数数列题目简介暴力遍历法双指针法求和公式间隔法的全部内容，更多相关LEETCODE内容请搜索靠谱客的其他文章。