双指针题目总结
leetcode27移除元素
关键字：快慢指针
- 双指针都定义在头部，快指针每次都+1，设置条件让慢指针不是每次都+1从而达到快慢的效果
本题思路：
这道题目设置的条件就是 当快指针指向目标值时慢指针停下来不走。
代码：
class Solution { public: int removeElement(vector<int>& nums, int val) { int slow = 0; //慢指针 int fast = 0; //快指针 int len = 0; for(;fast<nums.size();fast++){ //快慢指针开始前进 if(nums[fast] != val){ //慢指针前进的条件 nums[slow++] = nums[fast]; len++; } } return len; } };
leetcode344反转字符串
关键字：对撞指针
- 将双指针定义为左右指针，一个在头部一个在尾部，两个指针逐渐靠近，当两指针碰撞时结束循环
本题思路：
这道题是很多字符串题目的基低，必须当成常识，实现很简单
代码：
class Solution { public: void reverseString(vector<char>& s) { int left =0; //左指针 int right = s.size() -1; // 右指针 while(left<=right) { swap(s[left++],s[right--]);//对撞的过程 } } };
剑指Offer 05替换空格
关键字：新旧指针
- 一个指针指向旧容器的尾部，一个指针指向新容器的尾部，从后向前走，当两个指针相碰的时候结束过程
本题思路：
首先将字符串中的空格计数，然后resize字符串的大小，旧指针指向旧字符串的尾部，新指针指向新字符串的尾部，当旧指针指向空格时新指针开始向前遍历替换字符，当旧指针与新指针相碰的时候结束
代码：
class Solution { public: string replaceSpace(string s) { int count_blank =0; //记录空格的个数 for(int i =0;i<s.size();i++){ if(s[i] == ' ') count_blank++; } int oldptr = s.size() - 1; //旧指针指向旧字符串尾 s.resize(s.size() + count_blank*2); //扩大原字符串的大小 int newptr = s.size() - 1; //新指针指向新字符串尾 while(oldptr<newptr){ //对双指针的条件判断 if(s[oldptr] != ' '){ s[newptr--] = s[oldptr--]; }else{ // 旧指针指向空格的情况 s[newptr--] = '0'; s[newptr--] = '2'; s[newptr] = '%'; oldptr--; newptr--; } } return s; } };
leetcode151翻转字符串里的单词
关键字：对撞指针/快慢指针
- 对撞：将双指针定义为左右指针，一个在头部一个在尾部，两个指针逐渐靠近，当两指针碰撞时结束循环
- 快慢：双指针都定义在头部，快指针每次都+1，设置条件让慢指针不是每次都+1从而达到快慢的效果
本题思路：
这道题双指针其实不是解题的重点，重点是对于这道题的拆分，将一个大问题拆分为3各小问题，
第一个小问题就是去掉字符串里面的多余空格和字符串前后的空格
这个小问题利用快慢指针，利用快指针右移忽略掉前面的空格，然后快慢指针配合去掉多余空格，最后再利用resize去掉后面的空格即可
void delete_blank(string &s){ int slow = 0; int fast = 0; //去掉最左边的空格 while(s.size()>0 && s[fast] == ' ') fast++; //利用快指针去掉前面的空格 //去掉多余空格 //快慢指针配合去掉多余空格 for(;fast<s.size();fast++){ if(fast>1&&s[fast] == ' '&& s[fast -1] ==' '){ continue; } s[slow++] = s[fast]; } //去掉最后的空格 if(slow > 1 &&s[slow - 1] == ' '){ s.resize(slow - 1); }else{ s.resize(slow); } }
第二个小问题就是反转整个字符串
这个小题利用对撞指针，与之前leetcode344不同的是该题需要多设置两个参数，一个起始指针和一个结束指针，方便第三小问调用
void reversePart(string &s ,int start,int end){ int left = start; int right = end; while(left < right){ swap(s[left++],s[right--]); } }
第三个小问题就是反转字符串里面的字串
对局部使用对撞指针然后调用第二个小问，用代码来展示思路
string reverseWords(string s) { delete_blank(s); //第一个小问题 reversePart(s,0,s.size()-1); //第二个小问题 int word_start = 0; //局部起始指针 int word_end = 0; //局部结束指针 bool inwords =false; //某次循环是否再单词内部的标志 for(int i =0;i<s.size();i++){ if(!inwords){ //开始进入单词区间 word_start = i; inwords = true; } if(inwords && s[i] == ' '){ //根据空格确定局部结束指针的值 word_end = i -1; reversePart(s,word_start,word_end); inwords = false; } if(inwords && (i == s.size()-1) && s[i] != ' '){ //末尾的判断 word_end = i; reversePart(s,word_start,word_end); inwords = false; } } return s; }
leetcode206翻转链表
关键字：同步指针
- 两指针一前一后无条件同步前进，适用于对链表的操作
本题思路：
设置一个头指针指向null，其与head指针共同向后遍历调转head的next指针
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode * first = nullptr; ListNode * head_next; while(head){ head_next = head->next; head->next = first; first = head; head = head_next; } return first; } };
leetcode19 删除链表的倒数第N各节点
关键字：快慢指针
- 双指针都定义在头部，快指针每次都+1，设置条件让慢指针不是每次都+1从而达到快慢的效果
本题思路
本题设置的条件是在一开始，让快指针首先移动到n的位置，然后快慢指针同时前进，当快指针指向尾部的时候，慢指针就恰好指向要删除节点的位置
代码：
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode * first = new ListNode; first->next = head; ListNode * fastptr = first; ListNode * slowptr = first; for(int i =0;i<n;i++){ fastptr = fastptr->next; } fastptr = fastptr->next; //为了让慢指针指向删除的前一个节点，便于后续的删除操作 while(fastptr){ slowptr = slowptr->next; fastptr = fastptr->next; } slowptr->next = slowptr->next->next; return first->next; } };
面试题 02.07 链表相交
关键字：同步指针
- 两指针一前一后无条件同步前进，适用于对链表的操作
本题思路：
首先将两指针分别指向两个链表的头结点，然后将长的链表的同步指针后移，使之从指针位置开始链表长度相同，然后两指针同步后移，如果遇到了指向同一个节点的话就返回该指针。
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { //将两个链表对齐 int len_a = 0,len_b = 0; //设置虚拟头结点 ListNode * first_a = new ListNode; first_a->next = headA; ListNode * first_b = new ListNode; first_b->next = headB; ListNode * cur_a = first_a; ListNode * cur_b = first_b; while(cur_a->next){ cur_a=cur_a->next; len_a++; } while(cur_b->next){ cur_b = cur_b->next; len_b++; } //判断谁长谁就移 int diff = 0; if(len_a>len_b){ diff = len_a - len_b; while(diff--){ first_a = first_a->next; } }else{ diff = len_b - len_a; while(diff--){ first_b =first_b->next; } } //对齐操作结束 //双指针操作 while(first_a->next){ if(first_a->next == first_b->next){ return first_a->next; } first_a = first_a->next; first_b = first_b->next; } return NULL; } };
三数之和，四数之和
关键字：对撞指针
- 对撞：将双指针定义为左右指针，一个在头部一个在尾部，两个指针逐渐靠近，当两指针碰撞时结束循环
题解思路
对于三数之和与四数之和其实思路完全一样，两个对撞指针都是指向倒数的两个数，前面的一个数或者是两个数都是依靠外部的大for循环操作。对撞指针的移动条件就是这三个数/四个数的和与target的比较，大了就移动右指针，小了就移动左指针，因为我们一来是排好序的，所以这样移动指针
三数之和代码：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(),nums.end()); if(nums.size() < 3) return result; //元素不足三个直接退出 for(int i =0;i<nums.size()-2;i++){ //i是第一个数 int left = i+1; //第二个数 int right = nums.size() - 1; //第三个数 if(nums[i]>0){ //三数之和（或者说是target=0）的特色处理 如果排序后的第一个数都大于0 则不可能和为0 return result; } if(i>0 &&nums[i]==nums[i-1]){ //去重 continue; } //双指针开始操作 while(left<right){ if(nums[i] < 0-(nums[left] + nums[right])){ left++; while(right>left&&nums[left] == nums[left - 1]) left++; //去重 }else if(nums[i] > 0-(nums[left] + nums[right])){ right--; while(right>left&&nums[right] == nums[right + 1]) right--;//去重 }else{ //防止溢出 result.push_back({nums[i],nums[left],nums[right]}); while(right>left&&nums[left] == nums[left + 1]) left++;//去重 while(right>left&&nums[right] == nums[right - 1]) right--;//去重 left++; right--; } } } //去重 return result; } };
四数之和代码：
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); //排序 vector<vector<int>> result; for(int i =0;i<nums.size();i++){//第一个数 if(i>0&&nums[i] == nums[i - 1]){ continue; } for(int j = i + 1;j<nums.size();j++){//第二个数 if(j>i+1&&nums[j] == nums[j - 1]){ continue; } int left = j + 1; //第三个数 int right = nums.size() - 1; //第四个数 //双指针开始操作 while(left<right){ if(nums[i]+nums[j] > target - (nums[left] + nums[right])){ right--; while(left<right && nums[right] == nums[right + 1]) right--; //去重 }else if(nums[i]+nums[j] < target - (nums[left] + nums[right])){ left++; while(left<right && nums[left] == nums[left - 1]) left++; //去重 }else{ result.push_back({nums[i],nums[j],nums[left],nums[right]}); while(left<right && nums[right] == nums[right - 1]) right--; //去重 while(left<right && nums[left] == nums[left +1]) left++; //去重 left++; right--; } } } } return result; } };
两数之和
关键字：对撞指针
- 对撞：将双指针定义为左右指针，一个在头部一个在尾部，两个指针逐渐靠近，当两指针碰撞时结束循环
题解思路：
一开始的写法
vector<int> twoSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int left = 0; //指向数组头 int right = nums.size() - 1; //指向数组尾 while(left<right){ //当两个指针对撞结束循环 if(nums[left] + nums[right] > target){ //大于目标值就左移右指针 right--; }else if(nums[left] + nums[right] < target){//小于目标值就右移左指针 left--; }else{ return vector<int>{left,right}; //等于目标值时，返回左右指针 其实写这个的时候已经感觉有点不对劲了 } } return {}; }
测试
测试一下：nums = [2,7,11,15] target = 9
输出正确
然后自信的提交代码。。。
解答错误，查看错误，
发现如果nums本来无序的话，则我这个方法不行
分析原因：
看了下题目，对比了三数之和、四数之和与两数之和的区别，发现他俩因为是返回的值，所以使用sort标准库函数排序是不影响输出结果的，而这道题两数之和，是返回其值的索引值，故对nums排序是大错特错的，估计我是做三数之和与四数之和做魔怔了
改正：
由于两数之和是返回索引值，故不能动数组本身的相对位置，于是我想到了map容器，让key保存值，value保存索引值，这样一来，当将nums中的数据插入map时，又可以自动给nums的数据排序，又可以记录nums里面数据的索引值，由于nums中的数据可以重复，故我使用multimap（唯一可以重复key的map类型容器）。
代码：
vector<int> twoSum(vector<int>& nums, int target) { multimap<int,int> temp; //用来存放nums的值和索引值 int index = 0; //记录索引值 for(auto val : nums){ temp.insert(pair<int,int>(val,index++)); //插入到multimap中自动排序的操作 } multimap<int,int>::iterator left = temp.begin(); //将双指针定义为迭代器 multimap<int,int>::iterator right = --temp.end(); while(left != right){ //不可以写成left<right 该迭代器没有定义此操作 if(left->first + right->first > target){ //后面的思路就与上面的思路一样 right--; }else if(left->first + right->first < target){ left++; }else{ return vector<int>{left->second,right->second}; //返回索引值 } } return vector<int>{}; }
收获：
之前觉得双指针有点抽象，但经过了三数之和、四数之和、还有自己重新用双指针解决两数之和后脑子里面对双指针的思路变得清晰了起来，并且对map的操作更熟悉了
