数据结构与算法：双指针之“最长连续不重复子序列” +位运算之“求二进制中第k个数字”、“求二进制表示”、“二进制中1的个数” +整数离散化
双指针：
简介
常见问题分类：
对于一个序列，用两个指针维护某一段特定的区间
对于两个序列，维护某种次序（譬如归并排序中合并两个有序序列的操作）
双指针算法的最核心点在于，将O(N^2)的暴力算法降为O(N)的算法。
for(int i=0,j=0;i<n;i++)
{
while(j<i&&check(i,j))j++;
//具体问题处理逻辑
}
求最长连续不重复子序列
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
//j在左边，i在右边。i表示遍历的数组的终点。j表示以i为右边界，不重复的连续的数组最远能达到左边多远的下标位置。 那么j就有一种单调性。当i往右移动的时候，j只能向右移动。
int a[N];
int s[N];//类似哈希表，s[i]=a[i]在动态数组中出现的次数
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int res=0;
for(int i=0,j=0;i<n;i++)
{
s[a[i]]++;
while(s[a[i]]>1)//重复的一定是a[i]
{
s[a[j]]--;
j++;
}
res=max(res,i-j+1);
}
cout<<res<<endl;
return 0;
}
作者：ACwe
链接：https://www.acwing.com/activity/content/code/content/6964503/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。位运算：
求二进制中第k位数字
n>>k&1
二进制表示
一个十进制数x，其二进制位数为log2(x)，通过以下代码可以输出x的二进制数表示
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
cin>>x;
for(int k=log2(x);k>=0;k--) cout<<(x>>k&1);
return 0;
}二进制中1的个数
#include<bits/stdc++.h>
using namespace std;
int lowbit(int x)
{
return x&(-x);
}
int main()
{
int n,x;
cin>>n;
while(n--)
{
cin>>x;
int ans=0;
while(x)
{
x-=lowbit(x);
ans++;
}
cout<<ans<<" ";
}
return 0;
}整数离散化
简介
vector<int> a;//存储所有待离散化的值
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end())//去除重复元素
//其中unique(a.begin(),a.end())返回的是所有不重复的元素的最后一个元素的下标
//并将重复的元素都挪到这个下标后一直到序列结尾。所以erase去除掉下标到序列结尾之间的数即可
//二分求出x对应的离散化的值，找到第一个≥x的位置
int find(int x)
{
int l=0,r=a.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
return r+1;
}区间和
##include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef pair<int,int> pii;
int a[N],s[N];
vector<pii>adds,querys;
int find(int x)
{
int l=0,r=x;
int mid=l+r>>1;
return r+1;
}
int main()
{
return 0;
}