优化需求：寻找和为目标数的连续平方数序列的Java代码

问题分析 #

原代码的核心问题是时间复杂度过高：外层循环遍历到目标数t（当t为大数时，循环次数会达到数万甚至更多），内层还嵌套while循环，整体为O(n²)复杂度，处理大数时必然出现明显卡顿。

优化思路 #

采用**滑动窗口（双指针）**思路优化，同时缩小起始值的遍历范围：

• 起始值left的上限无需到t：若单个平方数left²已大于t，不可能成为有效序列的起点，因此left只需遍历到√t即可。
• 双指针维护窗口平方和：
  • 当窗口内平方和小于t时，右移右指针right，加入新的平方数；
  • 当平方和大于t时，右移左指针left，减去左边的平方数；
  • 当平方和等于t时，记录当前窗口的序列。

这种方法的时间复杂度为O(√t)，因右指针的增长速度是平方级的，不会无限遍历，效率较原代码提升显著。

优化后的代码 #

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        findConsecutiveNumbersWithSumOfSquares(t);

        scanner.close();
    }

    private static void findConsecutiveNumbersWithSumOfSquares(int t) {
        int left = 1;
        long currentSum = 0; // 用long避免大数平方和溢出
        int maxRight = (int) Math.sqrt(t) + 1; // 右指针最大范围

        for (int right = 1; right <= maxRight; right++) {
            currentSum += (long) right * right;

            // 平方和超过目标值时，移动左指针缩小窗口
            while (currentSum > t) {
                currentSum -= (long) left * left;
                left++;
            }

            // 找到符合条件的连续序列
            if (currentSum == t) {
                printConsecutiveNumbers(left, right);
            }
        }
    }

    private static void printConsecutiveNumbers(int start, int end) {
        System.out.print("[");
        for (int i = start; i <= end; i++) {
            if (i != start) {
                System.out.print(", ");
            }
            System.out.print(i);
        }
        System.out.println("]");
    }
}

代码说明 #

1. 用long存储平方和：避免t较大时，多个平方数相加导致int类型溢出（例如t=147439时，连续平方和可能超过int最大值2147483647）。
2. 缩小指针范围：maxRight设为√t+1，减少不必要的循环次数。
3. 滑动窗口逻辑：通过动态调整左右指针，避免了原代码中重复计算平方和的问题，每一步操作均为O(1)，整体效率大幅提升。
4. 输出格式对齐示例：调整为方括号包裹的格式，例如输入25时输出[3, 4]和[5]。

测试验证 #

• 输入5：输出[1, 2]
• 输入29：输出[2, 3, 4]
• 输入25：输出[3, 4]、[5]

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