基础算法

f

排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并

快速排序和归并排序的思想

区间和,需要用到离散化的知识,可以关注一下,就是用二分先离散化,然后求离散化的前缀和,对于每次询问,直接找到对应在离散化的位置然后相减即可.

寻找最长连续不重复子序列

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin >> n;
    vector<int>v;
    for(int i = 0;i<n;i++)
    {
        int x;cin >> x;
        v.push_back(x);
    }
    // 左右指针 代表当前位置
    int p = 0,q = 0;
    int mx= 0;
    map<int,int>mp;
    for(int i = 0;i<n;i++)
    {
        int nw = v[i];///当前数字
        q = i;
        if(mp[nw]==0)//未访问
        {
            mp[nw] = 1;
            
        }else{//已经存在
        // 存在就 找到为止
           while(v[p++]!=nw)
           {
               mp[v[p-1]] = 0;
           }
            mp[nw] = 1;// 这里需要设置为1 代表包含此时访问的结点
        }
        mx = max(mx,q-p+1);
    }
    cout << mx;
    return 0;
}