双指针算法 实用i,j两个变量，不会退的扫描一个数组 常规写法

for(int i=0,j=0,i<n;i++){ while(j<i&&check(i,j)) j++; }

这是i,j从0开始扫，j<i的扫法

for(int i=0,j=n-1;i<j;i++){ while(check()) j--; }

这是i,j分别两端的写法 或者也能这样写

int i=0,j=-1; while(i<j){ if(check(i,j)) i++; else j--; }

选择leetcode上7条题目为例 //: # (推荐题解模板，请替换blablabla等内容 ^^)

leetcode 167

题目描述

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

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

说明:

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

样例

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

---

算法1

(双指针) $O(n)$

今天刚学习了双指针的模板，来练一下手，对于排序的数组，可以使用双指针来压缩搜索空间，起点分别设置在原数组两端，当l右移动可以时候,numbers[i]+numsbers[j]变大，r左移时候,和减少，不停的调整知道找到,l,r由于下标从1开始，l,r需要+1

C++ 代码

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int n=numbers.size(); for(int i=0,j=n-1;i<j;i++){ while(numbers[i]+numbers[j]>target) j--; if(numbers[i]+numbers[j]==target) return vector<int>({i+1,j+1}); } return vector<int>({}); } };

这么写可以得到结果，但是不够规范，对于要返回的值最好放在一个变量里面，变量j,i可读性不强，换成l,r

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { vector<int> res; int n=numbers.size(); for(int l=0,r=n-1;l<r;l++){ while(numbers[l]+numbers[r]>target) r--; if(numbers[l]+numbers[r]==target) { res.push_back(l+1),res.push_back(r+1); return res; } } return res; } };

leetcode 633

题目描述

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

样例

示例1: 输入: 5 输出: True 解释: 1 * 1 + 2 * 2 = 5 示例2: 输入: 3 输出: False

---

算法1

(双指针) $O(n)$

接167题，也是双指针的模板题，条件是平方和相同，改变判断移动的条件即可， ####遇到的坑点： #####首先平方和等于c，a,b都不可能大于$sqrt(c)$ ，因此上边界可以定义位c的开根号再转换为整数， #####其次，a,b的数值是可以相同的，因此i,j不再是模板的i<j,而是i<=j; #####还有，$a^2+b^2$仍然可能超出int的范围，因此i,j最好一开始就定义为int

C++ 代码

class Solution { public: bool judgeSquareSum(int c) { bool res = false; for(long i=0,j=sqrt(c);i<=j;i++){ while(i*i+j*j>c) j--; if(i*i+j*j==c) { res = true; return res; } } return res; } };

---

#leetcode 345 //: # (推荐题解模板，请替换blablabla等内容 ^^)

题目描述

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

样例

示例 1: 输入: "hello" 输出: "holle" 示例 2: 输入: "leetcode" 输出: "leotcede" 说明: 元音字母不包含字母"y"。

---

算法1

(双指针) $O(n)$

接着前面的167， 633题，依然是双指针题，这次的模板类似于快排的写法，快排就是找到两个左右侧大于和小于枢纽的进行交换，这道题则是找到两个元音开始比较，非常类似，i,j指针分别两端开始，指向中间，直到i<j不成立

C++ 代码

class Solution { public: string reverseVowels(string s) { int l = 0,r=s.size()-1; while(l<r){ while(s[l]!='a'&&s[l]!='e'&&s[l]!='i'&&s[l]!='o'&&s[l]!='u'&&s[l]!='A'&&s[l]!='E'&&s[l]!='I'&&s[l]!='O'&&s[l]!='U'&&l<=r) l++; while(s[r]!='a'&&s[r]!='e'&&s[r]!='i'&&s[r]!='o'&&s[r]!='u'&&s[r]!='A'&&s[r]!='E'&&s[r]!='I'&&s[r]!='O'&&s[r]!='U'&&l<=r) r--; if(l<r) swap(s[l],s[r]); l++,r--; } return s; } };

###坑点

题目并没有告诉原因字母包括大小写，所以元音有10种而不是五种再初始代码种，所有的字母分别比较，没有用一个数据存储下来，代码写起来很长，也容易出错，修改也不方便，改进方法参考yxc的版本，将字母放于数组，并使用哈希表来判断 class Solution { public: string reverseVowels(string s) { vector<char> vowels = {'a','e','i','o','u','A','E','I','O','U'}; unordered_set<char> S;//建立一个集合，用来判断当前元素是否在集合中，来判断是否元音 for(auto c:vowels){ S.insert(c); } int l = 0,r=s.size()-1; while(l<r){ while(!S.count(s[l])&&l<=r) l++; while(!S.count(s[r])&&l<=r) r--; if(l<r) swap(s[l],s[r]); l++,r--; } return s; } };

leetcode 88

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

样例

输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]

---

算法1

(双指针) $O(n)$

这道题依然可以用双指针来做，非常类似于归并排序中将两个数组合并的那一步，需要开辟一个新的变量存放合并后的数组，最后再将数组传回nums1中即可

C++ 代码

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { vector<int> n3(m+n); int i=0,j=0,k=0; while(i<m&&j<n){ if(nums1[i]<nums2[j]) n3[k++]=nums1[i++]; else n3[k++]=nums2[j++]; } while(i<m) n3[k++]=nums1[i++]; while(j<n) n3[k++]=nums2[j++]; nums1 = n3; } };

在上面的仿归并算法中，需要临时一个构建一个数组，空间复杂度不是常数，通过观察题，没有充分利用题目所给的条件，nums1已经开够了足够大，如果直接在nums1上合并，便不需要额外的空间，而如果从前往后合并，要么会覆盖元素得到错误结果，要么元素整体后移导致时间复杂度上升n^2，再通过观察，如果从后往前合并的方式，则不会覆盖，也不会时间复杂度退化，是理想的解法，时间O(n)，空间常数

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p=m-1,q=n-1,cur=m+n-1; while(p>=0&&q>=0) nums1[cur--]=nums1[p]>nums2[q]?nums1[p--]:nums2[q--]; while(q>=0) nums1[cur--] = nums2[q--]; } };

---

leetcode 144

题目描述

给定一个链表，判断是否存在环。

进一步：能否只使用额外 O(1)O(1) 的空间？

思路

经典的快慢指针，类似于操场跑圈，如果两人一块一慢，最终肯定会相遇，如果不是环形的，最终都会到达终点。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { if(!head||!head->next) return 0;//如果空链表或者只有一个元素的链表，必然不成环 ListNode *first = head,*second = first->next;//first是块指针，一次移动1，second是慢指针，一次移动2 while(first&&second){//快慢都到达终点停止 if(first==second) return true;//相遇，成环 first = first->next;//快指针移动 second = second->next; if(second) second = second->next;//慢指针移动 } return false; } };

另一种写法

在判断是否成环时候除了找到成立情况退出外，也可以反过来写，找到不成了情况退出，找不到就是成立

class Solution { public: bool hasCycle(ListNode *head) { if(!head||!head->next) return 0; ListNode *l = head,*r = l->next; while(l!=r){ if(r==NULL||r->next ==NULL) return false; l=l->next,r=r->next->next; } return true; } };

leetcode 680

题目描述

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串

样例

示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解释: 你可以删除c字符。 注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

---

算法1

(双指针) $O(n)$

思路

依然是双指针算法，裸的判断回文串的进阶版本，对于裸的回文串，直接套双指针模板即可，而对于要删除一个字母的情况，当碰到不想等情况时候，可以删除i,也可以删除j因此有两种情况，而且只能删除一次，因此我们可以分别判断删除i和j，只要有一个变成回文串，就成立，而删除i,j结构基本类似，只是i,j起点不同，因此创建一个函数专门用来比较剩余部分是否是回文串。

C++ 代码

class Solution { public: bool validPalindrome(string s) { int i=0,j=s.size()-1; while(i<j){ if(s[i]!=s[j]) return isPalindrome(s,i+1,j)||isPalindrome(s,i,j-1); i++,j--; } return true; } bool isPalindrome(string s,int i,int j){//判断回文串 while(i<j){ if(s[i]!=s[j]) return false; i++,j--; } return true; } };

leetcode 524

题目描述

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

样例

示例 1: 输入: s = "abpcplea", d = ["ale","apple","monkey","plea"] 输出: "apple" 示例 2: 输入: s = "abpcplea", d = ["a","b","c"] 输出: "a"

---

算法1

(双指针) $O(n)$

C++ 代码

class Solution { public: string findLongestWord(string s, vector<string>& d) { if(d.size()==0) return ""; string res=""; for(auto sub:d){ if(issubstr(s,sub)==true) if(sub.size()>res.size()||sub.size()==res.size()&&sub<res) res = sub; } return res; } bool issubstr(string s,string d){ int i,j; for( i=0,j=0;i<s.size();i++){ if(s[i]==d[j]) j++; if(j==d.size()) break; } //cout<<j<<' '<<d.size()<<endl; if(j>=d.size()) return true; return false; } };

改进

class Solution { public: string findLongestWord(string s, vector<string>& d) { //if(d.size()==0) return ""; string res=""; for(auto sub:d) if(issubstr(s,sub)==true) if(sub.size()>res.size()||sub.size()==res.size()&&sub<res) res = sub; return res; } bool issubstr(string s,string d){ int i,j; for( i=0,j=0;i<s.size();i++) if(s[i]==d[j]) j++; return j==d.size(); } };