【数据结构c++】双指针（九）

1. 双指针

• 两数之和 II - 输入有序数组： https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
  
  

  class Solution
  {
  public:
  	vector<int>twoSum(vector<int>&numbers, int target)
  	{
  		int low = 0, high = numbers.size()-1;
  		while(low < high)
  		{	
  			int sum = numbers[low] + numbers[high];
  			if (sum == target)
  			{
  				return {low+1, high+1};
  			}
  			else if (sum < target)
  			{
  				++low;
  			}
  			else
  			{
  				--high;
  			}
  		}
  		return{-1, -1};
  	}
  
  };
  

  

• 合并两个有序数组： https://leetcode-cn.com/problems/merge-sorted-array/
  

  

  class Solution {
  public:
      void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
          int p1 = 0, p2 = 0;
          int sorted[m + n];
          int cur;
          while (p1 < m || p2 < n) {
              if (p1 == m) {
                  cur = nums2[p2++];
              } else if (p2 == n) {
                  cur = nums1[p1++];
              } else if (nums1[p1] < nums2[p2]) {
                  cur = nums1[p1++];
              } else {
                  cur = nums2[p2++];
              }
              sorted[p1 + p2 - 1] = cur;
          }
          for (int i = 0; i != m + n; ++i) {
              nums1[i] = sorted[i];
          }
      }
  };
  

  

• 平方数之和： https://leetcode-cn.com/problems/sum-of-square-numbers/
  
  

  class Solution {
  public:
      bool judgeSquareSum(int c) {
          long left = 0;
          long right = (int)sqrt(c);
          while (left <= right) {
              long sum = left * left + right * right;
              if (sum == c) {
                  return true;
              } else if (sum > c) {
                  right--;
              } else {
                  left++;
              }
          }
          return false;
      }
  };
  

• 通过删除字母匹配到字典里最长单词： https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/
  
  

  class Solution {
  public:
      bool isSubsequence(string s, string t) {
          // 判断 t 是否是 s 的子序列
  
          int n = s.size(), m = t.size();
          
          // 如果 t 长度大于 s，一定不是子序列
          if(m > n) return false;
  
          // 记录当前 s 中匹配到了哪个位置
          int i = 0;
          for(char ch : t) {
              while(i < n && s[i] != ch) i++;
              if(i >= n) return false;
  
              // 此时 s[i] = ch，下次要从 s[i + 1] 开始匹配
              i++;
          }
  
          return true;
      }
  
      string findLongestWord(string s, vector<string>& dictionary) {
          // 更长的、字典序更小的排在前面，这样一旦找到，就是结果
          sort(dictionary.begin(), dictionary.end(), [&](string &a, string &b) {
              if(a.size() == b.size()) return a < b;
              return a.size() > b.size();
          });
  
          for(string &t : dictionary) {
              if(isSubsequence(s, t)) return t;
          }
  
          // 如果没找到
          return "";
      }
  };