题目链接:https://leetcode.cn/problems/sum-of-square-numbers/description/
我的思路
知道要用双指针法,但也还是被题目给吓到了,给的c的范围是0到2的31次方-1,感觉从0开始遍历的话复杂度太高了。一开始想着遍历范围是从0到c/2,但感觉这样还是太大。也想过范围为0到根号c,但以为leetcode无法引入其他的库来执行均方根操作,所以一直卡在这,遂去看题解了。
纠正
- 枚举法:枚举a=0,1,2,…,把式子变成$b=\sqrt{(c-a^2)}$,只要b是整数的话,就返回True,但a能一直枚举下去吗?不可以,如果枚举到$2a^2>c$的话,仍没有找到合适的b,就停止,证明:
此时$a^2>c-a^2$,假如继续枚举能找到符合等式的a和b,比如a=5, b=3,那么之前在枚举到a=3时,也能发现a=3, b=5符合等式,矛盾。所以当枚举到$2a^2>c$时,后面不可能找到符合等式的a和b。
- 双指针法:同样也需要明确指针的活动范围,应该是0到$int(\sqrt c)$,把左指针放到0,右指针放到$int(\sqrt c)$,然后求两指针的平方和,如果数值小于c,则把左指针右移,反之把右指针左移
反思
- Leetcode里也是可以引入一些常用库的,比如math,实现求平方根的操作
- isqrt函数:能将sqrt的值转化为整数,向下求整
- 显然指针法的耗时会比枚举法要少很多,因此在解决此类问题时不应该一股脑栽进笨方法中开始遍历枚举,而是要想一想是否能有其他更优化的办法
结果
枚举法:92ms, 28.96%; 17.5MB, 69.68%
双指针法:63ms, 64.85%; 17.45MB, 85.4%