斐波那契连续子数组和判定代码优化问询：复用前序计算结果优化双指针初始化逻辑

Great question! The original code wastes a ton of computation by resetting the two pointers and sum calculation from scratch every time we check a new integer. On top of that, the recursive fib function is highly inefficient due to repeated redundant calculations. Let’s fix both issues with a state-reusing approach that builds on previous checks instead of starting over.

Key Optimization Ideas #

• Precompute Fibonacci Numbers: Replace the recursive fib function with a dynamically growing list of Fibonacci numbers. This cuts out redundant calculations and lets us access any Fibonacci number in O(1) time.
• Reuse Window State: Instead of resetting L_pointer, R_pointer, and the sum for each new n, we maintain these values across checks. When moving from n to n+1, we only adjust the existing window (expand right if the sum is too small, shrink left if it’s too large) instead of starting fresh.

Optimized Code #

def main():
    # Initialize Fibonacci sequence: fib_list[i] maps to fib(i+1) in the original code
    fib_list = [1, 1]  # fib(1)=1, fib(2)=1
    L = 0  # Corresponds to original L_pointer=1
    R = 1  # Corresponds to original R_pointer=2
    current_sum = fib_list[L]  # Initial sum matches original code's starting value (fib(1)=1)

    def can_represent(n):
        nonlocal fib_list, L, R, current_sum

        while True:
            if current_sum == n:
                return True
            elif current_sum < n:
                # Expand the right end of the window
                current_sum += fib_list[R]
                R += 1
                # Generate next Fibonacci number if we've reached the end of our list
                if R >= len(fib_list):
                    next_fib = fib_list[-1] + fib_list[-2]
                    fib_list.append(next_fib)
            else:
                # Shrink the left end of the window
                if L >= R:
                    # Window can't shrink further, sum doesn't match n
                    return False
                current_sum -= fib_list[L]
                L += 1

    n = int(input())
    while can_represent(n):
        n += 1
    print(n)

if __name__ == "__main__":
    main()

Explanation #

1. Fibonacci Sequence Management: We start with the first two Fibonacci numbers and dynamically add new ones only when needed. This avoids the exponential overhead of recursive Fibonacci calculations.
2. Stateful Window Adjustment:
   • For each new n, we tweak the existing window instead of resetting it. If the sum is too small, we expand the right end by adding the next Fibonacci number.
   • If the sum is too large, we shrink the left end by subtracting the leftmost number in the window.
   • We only return False when the window can’t shrink further and the sum still doesn’t match n.
3. Bug Fix: The original code had a typo (L_poiner instead of L_pointer), which is corrected here to ensure proper execution.

Example Walkthrough (Input = 13) #

• When checking n=13, the window will adjust to include the single Fibonacci number 13 (sum equals 13), so can_represent(13) returns True.
• For n=14, we start with the sum 13 from the previous check. Since 13 < 14, we add the next Fibonacci number (21) to get a sum of 34. Now 34 >14, so we subtract 13 to get 21, then subtract 8 to get 13, then subtract 5 to get 8, then subtract 3 to get5, then subtract2 to get3, then subtract1 to get2, then subtract1 to get0. At this point, L >= R so we return False, meaning 14 is the first number that can’t be represented.

内容的提问来源于stack exchange，提问作者wallshock