题目

image.png
image.png

题解

双指针

这道题有点偏数学方面，我的思路是偏向双指针，而且是普通的双指针，左指针指向最小数，也就0， 而右指针的指向数字就需要动动脑子。需要一个合适的数字作为右指针的指向，最开始我轻题啦，当数据量变多时就需要照顾到算法如何快速分辨出。也就是这道题是在考我们如何让算法快速分别出，而我最终选择右指针指向数字c的平方根向下取整。这样就会保持搜索范围很小

最开始的版本

  1. /**
  2.  * @param {number} c
  3.  * @return {boolean}
  4.  */
  5. var judgeSquareSum = function(c) {
  6.     let l = 1;
  7.     let r = Math.floor(Math.sqrt(c))
  8.     let sum = '';
  9.     while(r > -1 && sum != c) {
  10.         sum = l * l + r * r
  11.         if(sum > c) {
  12.             r--;
  13.             continue;
  14.         }
  15.         if(sum < c) {
  16.             l++;
  17.             continue;
  18.         }
  20.     }
  21.     return sum == c 
  22. };

但是呢这个算法运行时间还是很慢

  1. /**
  2.  * @param {number} c
  3.  * @return {boolean}
  4.  * 
  5.  */
  6. var judgeSquareSum = function(c) {
  7.     let l = 0;
  8.     let r = Math.floor(Math.sqrt(c))
  9.     let sum = '';
  10.     while(l <= r) {
  11.         sum = l * l + r * r;
  12.         if(sum == c)return true;
  13.         if(sum > c) {
  14.             r--;
  15.             continue;
  16.         };
  17.         if(sum < c) {
  18.             l++;
  19.             continue;
  20.         }
  21.     }
  22.     return false
  23. };

而这段算法中你觉得那里可以优化，最开始我觉的已经没有可以优化的啦，但是你看if判断是不是可以优化

  1. /**
  2.  * @param {number} c
  3.  * @return {boolean}
  4.  * 
  5.  */
  6. var judgeSquareSum = function(c) {
  7.     if(c < 0) return false;
  8.     let l = 0;
  9.     let r = Math.floor(Math.sqrt(c))
  10.     let sum = '';
  11.     while(l <= r) {
  12.         sum = l * l + r * r;
  13.         if(sum == c)return true;
  14.         else if (sum > c) r--;
  15.         else l++;
  16.     }
  17.     return false
  18. };

数学的方式解决