Adobe Flash与LeetCode633碰撞下的双指针法提速攻略

引言

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

classSolution{public:booljudgeSquareSum(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>classSolution{public:booljudgeSquareSum(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){returntrue;}elseif(sum < c){
                a++;// 和太小，增加a}else{
                b--;// 和太大，减少b}}returnfalse;}};

代码解释

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>classSolution{public:booljudgeSquareSum(int c){long a =0;long b =static_cast<long>(sqrt(c));// 显式转换更安全while(a <= b){long sum = a * a + b * b;if(sum == c)returntrue;
            sum < c ? a++: b--;}returnfalse;}};

示例验证

示例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)，完美解决超时问题。核心在于利用有序性减少不必要的计算。通过对比两种代码，相信读者也能对双指针拥有更进一步的理解。