引言

本文将对比一种低效超时的双指针遍历法和优化过后的双指针遍历法，旨在通过对比代码的方式加深对双指针方法的理解运用。话不多说先上源码（若只是想参考优化后代码可不看该部分）

class Solution {
public:
    bool judgeSquareSum(int c) {
    long a=0,b=0;
    long sum=0;
    int maxB=0;
    bool firstRecordMaxB=false;
    while(sum!=c)
    {
         if(a>maxB) break;//若a都遍历到b的最大值了还没有达成相等 则认为c不可分为两整数平方和
         if(sum>c)
         {
            if(firstRecordMaxB == false)
            {
                maxB = b;//记录b的最大值 
                firstRecordMaxB = true;
            }
            b=0;
            ++a;
            sum = a*a + b*b;
            if(sum == c) break;
         }
         ++b;
         sum = a*a + b*b;
    }
    
    return sum==c?true:false;
    }
};

---

问题分析

1. 错误的重置逻辑：

   • 当sum > c时，源代码将b重置为0并增加a，但这种方法需要重新遍历所有b，导致时间复杂度高达O©。
   • 示例：c=1e9时，需要遍历约3e4次（正确方法） vs 1e9次（你的方法）。

2. 逻辑错误：

   • firstRecordMaxB == true 应为 firstRecordMaxB = true（赋值而非比较）。

3. 低效的终止条件：

   • maxB未正确更新，导致无法有效限制搜索范围。

---

改进方案：双指针法（高效）

核心思路：

1. 初始化a=0，b=sqrt(c)（最大可能值）。
2. 根据a² + b²与c的比较，动态调整a和b：
   • sum < c → 增加a。
   • sum > c → 减少b。
   • sum == c → 找到解。

时间复杂度：O(√c)，仅需遍历约√c次。

---

正确代码实现

#include <cmath>

class Solution {
public:
    bool judgeSquareSum(int c) {
        long a = 0;
        long b = static_cast<long>(sqrt(c)); // b初始为最大可能值
        while (a <= b) {
            long sum = a * a + b * b;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                a++; // 和太小，增加a
            } else {
                b--; // 和太大，减少b
            }
        }
        return false;
    }
};

---

代码解释

1. 变量初始化：

   • a从0开始，b从sqrt(c)开始（最大可能的整数值）。
   • 使用long避免整数溢出。

2. 循环条件：

   • a <= b确保所有可能的组合都被检查。

3. 动态调整：

   • sum == c：找到解，返回true。
   • sum < c：当前和太小，需要增加a。
   • sum > c：当前和太大，需要减少b。

在C++中，sqrt(c)的返回类型是double，而我们需要将其转换为long类型。

---

为什么要用 static_cast<long>？

1. 类型明确性：

   • sqrt()函数的返回值类型为double，但我们需要整数类型的b。
   • static_cast<long>明确告诉编译器：这里需要将double强制转换为long类型。

2. 避免隐式转换的歧义：

   • 直接写long b = sqrt(c)依赖隐式类型转换，可能在某些编译器中出现警告。
   • 显式转换能消除编译器警告（如"隐式转换可能丢失精度"）。

3. 向下取整的正确性：

   • sqrt(5)的值为2.236，转换为long后会截断小数部分，得到2。
   • 这恰好是我们需要的行为：b的最大可能值为floor(sqrt(c))。

---

为什么不能直接写 long b = sqrt(c)？

• 语法合法性：
  直接赋值是合法的，但存在潜在问题：

  long b = sqrt(c);  // 隐式转换double→long
  

  • 问题1：当sqrt(c)返回的浮点数过大时，可能超出long的范围（但题目中c ≤ 2^31-1，平方根最大为46340，不会溢出）。
  • 问题2：部分编译器会对隐式转换发出警告，显式转换更规范。

---

代码示例对比

隐式转换（合法但有警告风险）

long b = sqrt(c);  // 依赖隐式转换

显式转换（推荐写法）

long b = static_cast<long>(sqrt(c));  // 明确类型转换意图

---

关键总结

• 功能等价性：两种写法在功能上等价，但显式转换更符合现代C++规范。
• 代码健壮性：显式转换能避免隐式类型转换的潜在风险。
• 可读性：明确标注类型转换，提高代码可维护性。

---

最终代码优化

#include <cmath>

class Solution {
public:
    bool judgeSquareSum(int c) {
        long a = 0;
        long b = static_cast<long>(sqrt(c));  // 显式转换更安全
        while (a <= b) {
            long sum = a * a + b * b;
            if (sum == c) return true;
            sum < c ? a++ : b--;
        }
        return false;
    }
};

---

示例验证

示例1：c = 5

• a=0, b=2 → 0 + 4 = 4 < 5 → a=1.
• a=1, b=2 → 1 + 4 = 5 → 返回true.

示例2：c = 3

• a=0, b=1 → 0 + 1 = 1 < 3 → a=1.
• a=1, b=1 → 1 + 1 = 2 < 3 → a=2.
• a=2 > b=1 → 循环结束，返回false.

---

边界处理

• c=0：a=0, b=0 → 0 + 0 = 0 → 返回true.
• c=1：a=0, b=1 → 0 + 1 = 1 → 返回true.
• 大数测试：c=2147483647（2^31-1）也能高效处理。

---

总结

通过将双指针初始化为合理的范围，并动态调整指针位置，该算法将时间复杂度从O©优化至O(√c)，完美解决超时问题。核心在于利用有序性减少不必要的计算。通过对比两种代码，相信读者也能对双指针拥有更进一步的理解。