java - 给定一个数 N，N 是否可以表示为两个或多个连续的完全平方数之和？

Question

在我最近参加的计算机编程竞赛中，有一个问题，您必须确定数字 N(对于 1<=N<=1000)是否为回文方 block 。回文平方是可以正向和反向读取相同的数字，可以表示为两个或多个连续完全平方的和。例如，595 是一个回文，可以表示为 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2。

我知道如何确定数字是否为回文，但我在尝试弄清楚它是否可以表示为两个或多个连续平方数的总和时遇到了问题。

这是我尝试过的算法:

public static boolean isSumOfSquares(int num) {
         int sum = 0;
         int lowerBound = 1;

         //largest square root that is less than num
         int upperBound = (int)Math.floor(Math.sqrt(num)); 
         
         while(lowerBound != upperBound) {
             for(int x=lowerBound; x<upperBound; x++) {
                 sum += x*x;
             }
             
             if(sum != num) {
                 lowerBound++;
             }
             else {
                 return true;
             }
             sum=0;
                                                
         }
         
         return false;
     }

我的方法将上限设置为最接近数字的平方根，将下限设置为 1，并不断计算从下限到上限的平方和。问题是只有下限发生变化，而上限保持不变。

Answer 1

这应该是一种有效的算法，用于确定它是否是连续数字的平方和。

1. 从下限和上限 1 开始。当前平方和为 1。

   public static boolean isSumOfSquares(int num) {
       int sum = 1;
       int lowerBound = 1;
       int upperBound = 1;
   

2. 最大可能的上界是其平方小于或等于要测试的数的最大数。

   int max = (int) Math.floor(Math.sqrt(num));
   

3. While 循环。如果平方和太小，则添加下一个平方，递增 upperBound。如果平方和太高，则减去第一个平方，递增 lowerBound。如果找到号码就退出。如果不能表示为连续数的平方和，那么最终upperBound会超过max，返回false。

   while(sum != num)
   {
        if (sum < num)
        {
            upperBound++;
            sum += upperBound * upperBound;
        }
        else if (sum > num)
        {
            sum -= lowerBound * lowerBound;
            lowerBound++;
        }
        if (upperBound > max)
            return false;
   }
   
   return true;
   

5、11、13、54、181 的测试，和 595。是的，其中一些不是回文，但我只是测试连续数字部分的平方和。

1: true
2: false
3: false
4: true
5: true
11: false
13: true
54: true
180: false
181: true
595: true
596: false