LeetCode 633，167#双指针专题

标准分析步骤

• 1.分析题意：对于题目本身的描述，一些边界条件或者非法输入，提出自己的问题。像面试官表明你对问题已经有了一定的思考

  • 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2+b2=c

  • 0 <= c <= 2^31 - 1

  • 首先需要注意a^2超int的问题 可以使用double

  • 判断一个数是否为可开方数

• 2.描述一个大体思路：通常我们可以先给出一个最基本的暴力解法，再进一步去思考优化方法；

  • 暴力解法

    1. 从前往后枚举++i,j=i*i<=c

    2. 判断sqrt(c-j)是否是可开方数 sqrt(c-j)==(int)(sqrt(c-j))

  • 优化解法-双指针

    • i,j同时操作 时间复杂度<sqrt(n)

• 3.写代码：如果第二步做好了，那么这里其实就是把伪代码或者框图填充完；

  class Solution {
  public:
      bool judgeSquareSum(int c) {
          for(double i=0,j=0;j<=c;j=i*i)
          {
              //cout<<" "<<j<<" "<<(int)(sqrt(c-j))*(int)(sqrt(c-j))<<endl;
              if(sqrt(c-j)==(int)sqrt(c-j))
              {
                  return true;
              }
              i=i+1;
          }
          return false;
      }
  };
  class Solution {
  public:
      vector<int> twoSum(vector<int>& numbers, int target) {
          int i=0,j=numbers.size()-1;
          
          for(;i<=j;)
          {
              if(numbers[i]+numbers[j]==target)
                  break;
              else if(numbers[i]+numbers[j]<target)
                  i++;
              else
                  j--;
          }
          vector<int>temp;
          temp.push_back(i+1);
          temp.push_back(j+1);
          return temp;
      }
  };
  

• 测试：通过自己给的测试用例发现代码的潜在问题，也是面试考察中的一环。通常我们给出一个边界用例，再结合一个常规用例，一步一步地通过语言描述你的算法做了什么，并且可以在白板旁边标注当前的程序运行状态，来检验最后的答案是否正确；

  • 普通的样例走一遍流程 11
  • 边界值测试是否存在细节错误 2,147,483,648

• 简单分析一下算法的时间和空间复杂度。

  • 暴力解法

    • 时间：o（sqrt（n））
    • 空间：o（1）

  • 双指针

    • 时间：o（sqrt(n)）
    • 空间：o(1)

LeetCode 167 #双指针专题

• 分析题意：

  • 给定一个已按照*升序排列* 的有序数组，找到两个数使得它们相加之和等于目标数。

    函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

    说明:

    • 返回的下标值（index1 和 index2）不是从零开始的。//从1开始
    • 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。//不可以重复使用一个元素

    示例:

      输入: numbers = [2, 7, 11, 15], target = 9
      输出: [1,2]
      解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
  

• 解法：

  • 暴力解法

    • o(n2)找一遍

  • 技巧解法

    • 先标记一遍整个数组，记录值为其下标，然后从头往后找 target-a[i]是否存在标记，存在即可返回记录下标
    • 复杂度o(n)

  • 双指针解法

• 代码：

  • //技巧解法
    class Solution {
    public:
        vector<int> twoSum(vector<int>& numbers, int target) {
            map<int,int>mp;
            vector<int>ans;
            for(int i=0;i<numbers.size();i++)
            {
                mp[numbers[i]]=i+1;
            }
            for(int i=0;i<numbers.size();i++)
            {
                if(mp[target-numbers[i]]&&mp[target-numbers[i]]!=i)
                {
                    ans.push_back(i+1);
                    ans.push_back(mp[target-numbers[i]]);
                    break;
                }
            }
            return ans;
        }
    };
    //双指针解法
    class Solution {
    public:
        bool judgeSquareSum(int c) {
            unsigned int i=0,j=(int)sqrt(c);//注意sqrt以后是浮点型数据 必须强转
            for(;i<=j;)
            {
                if(i*i+j*j==c)//这里可能超int 2 31-1
                    return true;
                else if(i*i+j*j<c)
                    i++;
                else
                    j--;
            }
            return false;
            /*
            for(double i=0,j=0;j<=c;j=i*i)
            {
                //cout<<" "<<j<<" "<<(int)(sqrt(c-j))*(int)(sqrt(c-j))<<endl;
                if(sqrt(c-j)==(int)sqrt(c-j))
                {
                    return true;
                }
                i=i+1;
            }
            return false;
            */
        }
    };
    

LeetCode 633，167 #双指针专题

原文：https://www.cnblogs.com/wjs-ouc/p/14274557.html