和为s的连续正数序列.org

题目

思路

1.滑动窗口，时间复杂度 O(n)，每个元素只会进入窗口1次

2.前缀和 + 二分查找，时间复杂度 O(nlogn)

code

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:

        # 1.滑动窗口，时间复杂度 O(n)，每个元素只会进入窗口1次
        res = []
        left, right = 1, 1
        tot = 0
        while right < target: # 不能取到 target，序列至少要含有2个数
            tot += right
            right += 1
            if tot == target and right - left > 1:
                # 注意这里的 left、right范围
                res.append([k for k in range(left, right)])
            elif tot > target:
                while tot > target:
                    tot -= left
                    left += 1
                if tot == target and right - left > 1:
                    # 注意这里的 left、right范围
                    res.append([k for k in range(left, right)])
                    continue
        return res

        # 2.前缀和 + 二分查找，时间复杂度 O(nlogn)
        ssum = [0] * target
        for i in range(1, target):
            ssum[i] = ssum[i-1] + i
        # print(ssum)
        res = []
        for i in range(2, target): # i==4
            # for j in range(0, i):
            lo, hi = 0, i
            # 用二分查找优化搜索
            while hi >= lo:
                mid = (lo + hi) >> 1
                if ssum[i] - ssum[mid] == target and i - mid > 1:
                    res.append([k for k in range(mid + 1, i + 1)])
                    break
                elif ssum[i] - ssum[mid] > target:
                    lo = mid + 1
                elif ssum[i] - ssum[mid] < target:
                    hi = mid - 1
                # 直接暴力搜索，超时
                # if ssum[i] - ssum[j] == target and i - j > 1:
                #     res.append([k for k in range(j + 1, i + 1)])
                #     break
                # if ssum[i] - ssum[j] < target:
                #     break
        return res