方法解读
在尺取法中，有两种扫描方法：
- 反向扫描：
一个指针(i)从头到尾进行扫描，另一个指针(j)从尾到头进行扫描。
- 同向扫描：
两个指针i,j都是从头开始扫描，只不过是速度不同，我们也把这种方法称为快慢指针。快慢指针可以产生一个大小可变的滑动窗口。
反向扫描
891 · 有效回文 II
题目描述
给你一个字符串，在最多删去一个字符的情况下，判断该字符串是否为回文。
思路
我们还是用判断是否为回文的基本方法——反向指针法
用两个指针i，j。i指向字符串的头，j指向字符串的尾
如果两个指针指向的字符相等，那么就相对走一步——i ,j--
如果不相等，就有两种情况：
- 把i指向的字符删去——
i - 把j指向的字符删去——
j--
这两种情况我们都需要考虑的。
ac代码
代码语言：javascript复制cppclass Solution {
public:
bool validPalindrome(string &s) {
int i=0,j=s.size()-1;
while(i<j)
{
if(s[i]==s[j])
{
i ;
j--;
}
else//指向不同，进行下面两种情况的判断
break;
}
int a=i 1, b=j--;
//a,b是第一种情况，查找的是[i 1,j]
//i,j是第二种情况，查找的是[i,j-1]
while(a<b&&i<j)//他们之间的区间长度是一样的
{
if(s[a]==s[b]||s[i]==s[j])//只要满足其中一个条件就可以
{
a ;
b--;
i ;
j--;
}
else
return false;
}
return true;
}
};15. 三数之和
题目描述
给定一组数据，从这组数据中从中选取3个数——a,b,c。使得这三个数的和为0，即a b c=0。返回这样的三元组，要求返回的三元组中的数据不能有重复。
思路
暴力的循环肯定是时间复杂度太高，不能用。 该到题目可以用排序 双指针的算法，要注意题目中对返回三元组的去重。 排序之后，如果当nums[i]>0的时候，就不需要进行后面数的遍历了，因为对于一个升序的数组，后面的数据都是大于0的，其结果不会等于0。同时在遍历的时候，在判断下一个数据（nums[i 1]）的时候，也需要去重——即比较nums[i]与nums[i-1]不能相等。 双指针： 用i遍历数组中的元素——nums[i]看成a，用两个指针L,R控制b，c所在的区间即——nums[L]=b,nums[R]=c。
- 当a b c=0的时候，进入返回结果中，同时对区间进行去重，去重之后再进行迭代
- 当a b c>0的时候，我们想要把结果变小，就要缩短右边，在缩短右边的时候，先进行去重，然后再R--
- 当a b c<0的时候，我们想要把结果变大，就要缩短左边，在缩短左边的时候，先进行去重，然后再L
去重：循环比较自己和下一个数是否相等，即：nums[L]与nums[L 1],nums[R]与nums[R-1]进行比较。
代码语言：javascript复制cppclass Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(),nums.end());
int L,R;
for(int i=0;i<nums.size();i )
{
if(nums[i]>0)//后面不可能有数据使他们的和为0
break;
if(i>0&&nums[i]==nums[i-1])//当前数据不能和之前的数据相同——去重
continue;
//设置区间
L=i 1;
R=nums.size()-1;
while(L<R)
{
int sum =nums[i] nums[L] nums[R];
if(sum==0)
{
ret.push_back({nums[i],nums[L],nums[R]});
//去重
while(L<R&&nums[L]==nums[L 1])
L ;
while(L<R&&nums[R]==nums[R-1])
//下一个
R--;
L ;
R--;
}
else if(sum>0)
{
//去重
while(L<R&&nums[R]==nums[R-1])
R--;
//下一个
R--;
}
else
{
//去重
while(L<R&&nums[L]==nums[L 1])
L ;
//下一个
L ;
}
}
}
return ret;
}
};正向扫描
快慢指针
3061 -- Subsequence
题目描述
给你一组数，该组数的每个数的范围都是大于10小于100000的。再给定一个值S,找出最短的连续区间，使区间和大于或者等于S
思路
显然我们用快慢指针就可以解决这个问题，指针i，j。 i为左区间，j为右区间，sum为i到j的区间和。 当sum大于s时，停止扫描，记录区间的长度（同时进行区间长度的判断），然后i ，继续另一个空间，直到区间完全扫描完。 最后返回最短的区间长度。
ac代码
代码语言：javascript复制cpp#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
while (n--)
{
int v, s;
cin >> v >> s;
int len = v;
vector<int> a(v,0);
for (int i = 0; i < v; i )
cin >> a[i];
int i = 0, j = 0;
int sum = 0;
while (i<v&&j<v)
{
sum = a[j];
j ;
while(sum>=s)
{
sum -= a[i];
if (len > j - i)
len = j - i;
i ;
}
}
if (len == v)
cout << 0 << endl;
else
cout << len << endl;
}
return 0;
}234. 回文链表
题目描述
判断一个单链表是不是回文链表
思路
完整代码有注释
- 用快慢指针找出中间结点
- 把后一半链表逆置
- 遍历链表，进行判断
- 还原链表
- 时间复杂度O(N)，空间复杂度O(1)
ac代码
代码语言：javascript复制cppclass Solution {
public:
bool isPalindrome(ListNode* head) {
if(!head->next)
return true;
//获取中间结点
ListNode* mid= findMid(head);
//反转后半部分结点
ListNode* rmid= reverseList(mid);
//判断回文
ListNode* cur=rmid;
while(head&&cur)
{
if(head->val!=cur->val)
{
//反转恢复
reverseList(rmid);
//不是回文
return false;
}
head=head->next;
cur=cur->next;
}
//反转恢复
reverseList(rmid);
//是回文
return true;
}
ListNode* findMid(ListNode* h)
{
//快慢指针找到中间的结点
ListNode* s,*q;//s慢指针，q快指针
s=q=h;
while(q)
{
s=s->next;
q=q->next;
if(q)
q=q->next;
}
return s;
}
ListNode* reverseList(ListNode* h)
{
ListNode* cur=h->next;
ListNode* curpro=h;
while(cur)
{
ListNode* t=cur->next;
cur->next=h;
curpro->next=t;
//更新头
h=cur;
cur=t;
}
return h;
}
};多指针
洛谷P1102
题目描述
给定一组数和一个目标值C，从这组数中选取2个数A,B。求像A-B=C，这种种数对有多少个。
思路
- 多指针法
首先我们先排好序。 对于一个排好序的序列，如果该序列中没有重复的数字的话，完全可以用双指针解决该问题；但是因为可能会出现相同的数据，所以我们要用一个区间去控制这些相等的数。 因为排好数之后，数字是单调不减的，所以该区间会随着遍历往上增长。
- 二分
先排序O(nlogn)，依次遍历数组，把遍历的数据减去C,然后用二分查找观察减去的结果是否在原数据中。但是这样会超时，因为存在相同的数据，那么查找的时间的时间复杂度为O(KlogN),最bt的情况就是当k为n的时候，那么该算法的时间复杂度N2logNN^2logNN2logN,将超时
cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int bs(vector<int>& a, int t)
{
int i = 0, j = a.size() - 1;
int ret=0;
while (i <= j)
{
int mid = (i j) >>1;
if (a[mid] == t)
ret ;
else if (a[mid] < t)
{
i = mid 1;
}
else
{
j = mid - 1;
}
}
return ret;
}
int main()
{
int n, c;
cin >> n >> c;
vector<int> arr(n);
for (int i = 0; i < n; i )
cin >> arr[i];
sort(arr.begin(), arr.end());
int l=0, r=0;
long long ret = 0;
for (int i = 0; i < n; i )
{
ret =bs(arr, arr[i] - c);
}
cout << ret << endl;
return 0;
}- map
二分超时是因为重复的值导致的查找变慢，我们用map进行查找就可以，map的底层是红黑树，查找时复杂度O(logN)——查找的是arr[i]-c，map中存储的是arr[i]存储的时间复杂度O(NlogN),总体时间复杂度O(NlogN),多开了O(N)个空间。用哈希也可以的，空间浪费是更大了。
ac代码
代码语言：javascript复制cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n, c;
cin >> n >> c;
vector<int> arr(n);
for (int i = 0; i < n; i )
cin >> arr[i];
sort(arr.begin(), arr.end());
int l=0, r=0;
long long ret = 0;
for (int i = 0; i < n; i )
{
while (l < n && arr[l] - arr[i] < c) l ;//左闭
while (r < n && arr[r] - arr[i] <= c) r ;//右开
ret = r - l;
}
cout << ret << endl;
return 0;
}cpp#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main()
{
int n, c;
cin >> n >> c;
vector<int> arr(n);
map<int, int> m;
for (int i = 0; i < n; i )
{
cin >> arr[i];
m[arr[i]] ;
}
long long ret = 0;
for (int i = 0; i < n; i )
{
ret = m[arr[i] - c];
}
cout << ret << endl;
return 0;
}cpp#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
int main()
{
int n, c;
cin >> n >> c;
vector<int> arr(n);
unordered_map<int, int> m;
for (int i = 0; i < n; i )
{
cin >> arr[i];
m[arr[i]] ;
}
long long ret = 0;
for (int i = 0; i < n; i )
{
ret = m[arr[i] - c];
}
cout << ret << endl;
return 0;
}1. 两数之和
题目描述
给定一个数组num和一个目标值target，找到两个和为target的下标。
思路
先把数及其下标存入哈希表中，然后查找target-nums[i]的是不是在哈希表中。
注意：要查找的值不能是自己本身。具体的实现看下面的代码
ac代码
代码语言：javascript复制cppclass Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
unordered_map<int,int> m;
for(int i=0;i<nums.size();i )
{//先查找在插入
auto r=m.find(target-nums[i]);
if(r!=m.end())
{
return {r->second,i};
}
m[nums[i]]=i;
}
return ret;
}
};
