本文将探讨几种常见的数组和字符串处理技巧，包括双指针法、滑动窗口算法以及前缀和差分数组的应用。

双指针法

在数组中，双指针技术可以用来解决诸如删除重复项等问题。下面是一个简单的例子，展示了如何使用双指针来移除有序数组中的重复项：

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int slow = 0, fast = 0;
        while (fast < nums.size()) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }
};

滑动窗口算法

滑动窗口是一种优化的暴力解法，它通过维护一个窗口，并根据条件调整窗口大小来解决问题。以下是一个查找字符串中所有字母异位词的例子：

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map need, window;
        for (char c : p) need[c]++;
        int left = 0, right = 0, valid = 0;
        vector<int> res;

        while (right < s.size()) {
            char c = s[right++];
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) valid++;
            }

            while (right - left >= p.size()) {
                if (valid == need.size()) res.push_back(left);
                char d = s[left++];
                if (need.count(d)) {
                    if (window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        return res;
    }
};

前缀和与差分数组

前缀和数组可以帮助快速计算任意区间的元素之和，而差分数组则适用于频繁对区间进行增减操作的情况。

以下是使用差分数组实现航班预订统计的例子：

class Difference {
private:
    vector<int> diff;
public:
    Difference(const vector<int>& nums) {
        diff.resize(nums.size());
        diff[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    void increment(int left, int right, int val) {
        diff[left] += val;
        if (right + 1 < diff.size()) diff[right + 1] -= val;
    }

    vector<int> result() {
        vector<int> res(diff.size());
        res[0] = diff[0];
        for (int i = 1; i < diff.size(); i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
};

class Solution {
public:
    vector<int> corpFlightBookings(vector& bookings, int n) {
        vector<int> nums(n, 0);
        Difference df(nums);
        for (auto& booking : bookings) {
            int left = booking[0] - 1;
            int right = booking[1] - 1;
            int val = booking[2];
            df.increment(left, right, val);
        }
        return df.result();
    }
};

双指针,滑动窗口,前缀和,差分数组,C++