双指针

双指针

最长连续不重复子序列

https://www.acwing.com/problem/content/801/

#include <iostream>

using namespace std;

const int N = 100010;
int a[N], count[N];
int n, ans;

int main()
{
    //最长连续不重复子序列    
    cin >> n;
    //输入n个数
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0, j = 0; j < n; j++) {
        //count[a[j]] 就是第j个元素出现的次数
        count[a[j]]++;
        // i 向 j 靠近，直到找到和 j 重复的那个数退出循环
        //靠近的过程中，相当于舍弃了之前的那些的数字
        //所以把这些数字出现的次数 -1
        while (count[a[j]] > 1) {
            count[a[i]]--;  
            i++;        
        }
        ans = max(ans, j - i + 1);
    }

    cout << ans << endl;

    return 0;
}

按奇偶排序数组

https://leetcode.cn/problems/sort-array-by-parity-ii/

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& arr) {
        int even = 0;
        int odd = 1;
        int n = arr.size();
        //把数组中最后一个元素看作缓冲位
        //然后通过不断的判断最后一位的奇偶性
        //然后与对应位置的数交换
        //每次交换后相应的位置都会发生变化
        for (int i = 0; i < n && even < n && odd < n;) {
             if ((arr[n - 1] & 1) == 1) {
                swap(arr[n - 1], arr[odd]);
                odd += 2;
             } else {
                swap(arr[n - 1], arr[even]);
                even += 2;
             }
        }
        return arr;
    }
};