双指针算法

双指针算法：

一般分为两种：

第一种：两个指针在同一个序列，一般维护一个区间满足某种性质，比如下面的最长上升子序列那个算法

 1 #include <iostream>
 2 #include <vector>
 3 #include <unordered_map>
 4 
 5 using namespace std;
 6 
 7 const int N = 1e6+10;
 8 
 9 unordered_map<int,int> m;
10 vector<int> arr(N,0);
11 int n, res = 0;
12 
13 int main(){
14     cin >> n;
15     for(int i = 0;i < n;++i)
16         cin >> arr[i];
17         
18     //双指针常用写法 for while形式
19     //维护 [j ，i]区间没有重复元素
20     for(int i = 0, j = 0;i < n;++i){
21         m[arr[i]] ++;
22         while(j <= i && m[arr[i]] > 1){
23             -- m[arr[j]];
24             ++ j;
25         }
26         res = max(res, i-j+1);
27     }
28     
29     cout << res << endl;
30     
31     return 0;
32 }

View Code

第二种：两个指针在不同的序列，一般维护某个顺序，比如归并排序里面的合并

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 int n;
 8 vector<int> arr(1e6+10,0);
 9 vector<int> help(1e6+10,0);//辅助数组
10 
11 void unionsort(vector<int>& arr,int l,int r){
12     //递归出口
13     if(l >= r)return;
14     //递归地把左边一半和右边一半分别排好序
15     int mid = l + r >> 1;
16     unionsort(arr,l,mid);
17     unionsort(arr,mid+1,r);
18     //合并已经排好序的两部分
19     int i = l, j = mid + 1, k = 0;
20     while(i <= mid && j <= r){
21         if(arr[i] <= arr[j]) help[k++] = arr[i++];
22         else help[k++] = arr[j++];
23     }  
24     //将剩下的部分合并    
25     while(i <= mid)help[k++] = arr[i++];
26     while(j <= r)help[k++] = arr[j++];
27     //此时辅助数组已经排好序，复制回原数组
28     for(int i = l,j = 0;i <= r;++i,++j)arr[i] = help[j];
29 }
30 
31 int main(){
32     cin >> n;
33     for(int i = 0;i < n;++i)cin>>arr[i];
34     unionsort(arr,0,n-1);
35     for(int i = 0;i < n;++i)cout << arr[i] << " ";
36     return 0;
37 }

View Code