文章目录
27. 移除元素（经典）
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
//i是快指针 j是慢指针
int j=0;
for(int i=0;i<nums.size();i++){
if(nums[i]!=val){
nums[j]=nums[i];
j++;
}
}
return j;
}
};
844. 比较含退格的字符串（与上一题同理）
要倒着覆盖。
注意abc和abcc的情况，两个串要同时结束才能true。
class Solution {
public:
bool backspaceCompare(string s, string t) {
int num1=change(s);
int num2=change(t);
int i,j;
for(i=num1,j=num2;i<s.size()&&j<t.size();i++,j++){
if(s[i]!=t[j]) return false;
}
if(i==s.size()&&j==t.size()) return true;
else return false;
}
int change(string &s){
//i 快 j 慢
int num=0;int j=s.size()-1;
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='#'){
num++;
}else{
if(num) num--;
else s[j--]=s[i];
}
}
return j+1;//这里要注意
}
};
11. 盛最多水的容器（双指针）
解法：
双指针ij，分别指向头和尾。小的那个往中间走，每次存最大值，直到i=j。
直观理解：每次不是i走就是j走，那么相对小的那个会拖后腿，就走它。
严谨证明：来自参考1
较好理解的证明：来自参考2
class Solution {
public:
int maxArea(vector<int>& height) {
//双指针 让小的走，因为小的拖后腿
int ans=0;
int i=0,j=height.size()-1;
while(i<j)
{
ans=max(ans,(j-i)*min(height[i],height[j]));
if(height[i]<height[j]) i++;
else j--;
}
return ans;
}
};
15. 三数之和（排序+双指针）
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>>ans;
if(nums.size()<3) return ans;
for(int i=0;i<nums.size();i++)
{
if(i&&nums[i]==nums[i-1]) continue;
int ii=i+1,jj=nums.size()-1;
int last=0x3f3f3f3f;
while(ii<jj)
{
if(nums[ii]+nums[jj]<0-nums[i]) ii++;
else if(nums[ii]+nums[jj]>0-nums[i]) jj--;
else
{
if(last!=nums[ii])
{
ans.push_back(vector<int>{nums[i],nums[ii],nums[jj]});
last=nums[ii];
}
ii++,jj--;
}
}
}
return ans;
}
};
18. 四数之和（排序+双指针）
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<vector<int>>ans;
for(int i=0;i<nums.size();i++)
{
long long lastt=0x3f3f3f3f;
if((i&&nums[i]!=nums[i-1])||!i)
for(int j=i+1;j<nums.size();j++)
{
int ii=j+1,jj=nums.size()-1;
//防溢出
long long temp=nums[i]+nums[j];
//去重
if(temp==lastt) continue;
else lastt=temp;
long long need=target-temp;
int last=0x3f3f3f3f;
while(ii<jj)
{
long long tempp=nums[ii]+nums[jj];
if(tempp>need) jj--;
else if(tempp<need) ii++;
else
{
//里层循环的去重
if(last==0x3f3f3f3f||last!=nums[ii])
{
ans.push_back(vector<int>{nums[i],nums[j],nums[ii],nums[jj]});
last=nums[ii];
}
ii++,jj--;
}
}
}
}
return ans;
}
};
19. 删除链表的倒数第 N 个结点（双指针）
双指针。
假设链表长度为n，要删除倒数第x个，有指针i（前指针），j（后指针）。
设链表从1开始，指针从0开始。
j先走x+1步，则j在第x+1的位置。
然后ij同时往前走，当j=NULL时，此时j的位置在n+1，则i走了(n+1)-(x+1)=n-x，i的下一个就是n-x+1，即要删除的结点。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *temp=new ListNode(0);
temp->next=head;
ListNode *a=temp;
ListNode *b=temp;
//后指针
for(int i=0;i<=n;i++) a=a->next;
//两个指针一起走 当后指针走到结尾时，前指针在要删除的结点的前面
while(a!=NULL)
{
a=a->next;
b=b->next;
}
//当走到这一步是 b在要删除的结点前面
b->next=b->next->next;
return temp->next;
}
};
142. 环形链表 II（双指针）
题解如下：环形链表 II（双指针法，清晰图解）
代码：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow=head,*fast=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
//相遇
if(fast==slow)
{
fast=head;
while(fast!=slow)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
}
return NULL;
}
};
977. 有序数组的平方（左右双指针）
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i=0,j=nums.size()-1;
vector<int>ans;
int now=0;
while(i<=j){
if(nums[i]*nums[i]>nums[j]*nums[j]){
ans.push_back(nums[i]*nums[i]);
i++;
}
else{
ans.push_back(nums[j]*nums[j]);
j--;
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};