相向双指针

两个指针left=0, right=n−1，从数组的两端开始，向中间移动，这叫相向双指针

633.平方数之和

例题：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c

示例：输入：c = 5 输出：true 解释：1^1 + 2^2 = 5

class Solution {
public:
    bool judgeSquareSum(int c) {
        int r = sqrt(c);
        int l = 0;
        while (l <= r) {
            // 做差：防止溢出
            int diff = c - r * r - l * l;
            if (diff < 0)
                r--;
            else if (diff > 0)
                l++;
            else
                return true;
        }
        return false;
    }
};

定长滑动窗口

三步走：

• 入：下标为 i 的元素进入窗口，更新相关统计量。如果窗口左端点i − k + 1 < 0，即 i < k − 1，则尚未形成第一个窗口，重复第一步。
• 更新：更新答案。一般是更新最大值/最小值。
• 出：下标为 i − k + 1 的元素离开窗口，更新相关统计量，为下一个循环做准备。

1456.定长子串中元音的最大数目

例题：给你字符串 s 和整数 k。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数，元音字母为（a, e, i, o, u）

示例：输入：s = "abciiidef", k = 3 输出：3 解释：子字符串 "iii" 包含 3 个元音字母

class Solution {
public:
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
    int maxVowels(string s, int k) {
        int l = 0;
        int r = l + k - 1;
        int ans = 0;
        int temp = 0;
        for (int r = l; r < s.size(); r++) {
            if (isVowel(s[r])) {
                temp++;
            }
            if (r - l + 1 < k)
                continue;
            ans = max(ans, temp);
            if (isVowel(s[l])) {
                temp--;
            }
            l++;
        }
        return ans;
    }
};

3439.重新安排会议得到最多空余时间 I

例题：给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的会议时长，你的目的是移动会议后 最大化相邻两个会议之间的 最长连续空余时间。移动前后所有会议之间的相对顺序需要保持不变，而且会议时间也需要保持互不重叠。请你返回重新安排会议以后，可以得到的最大空余时间。

示例：输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5] 输出：2 解释：将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2]

class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime,
                    vector<int>& endTime) {
        int n = startTime.size();
        int ans = 0;
        vector<int> spaceArea(n + 1, 0);
        // 最优就是（k + 1）个会议块连到一起
        for (int i = 0; i < n + 1; i++) {
            if (i == 0)
                spaceArea[i] = startTime[0];
            else if (i == n)
                spaceArea[i] = eventTime - endTime[n - 1];
            else
                spaceArea[i] = startTime[i] - endTime[i - 1];
        }
        int l = 0;
        int sum = 0;
        for (int r = l; r < n + 1; r++) {
            sum += spaceArea[r];
            if (r - l < k)
                continue;
            ans = max(ans, sum);
            sum -= spaceArea[l];
            l++;
        }
        return ans;
    }
};

不定长滑动窗口

最长子数组

3.无重复字符的最长子串

题目：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

示例:输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int l = 0;
        unordered_map<char, int> map;
        // How to deal with ' '
        for (int r = l; r < s.size(); r++) {
            map[s[r]]++;
            while (map[s[r]] > 1) {
                map[s[l]]--;
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

最短子数组

209.长度最小的子数组

题目：给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其总和大于等于 target 的长度最小的子数组并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例：输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT_MAX;
        int l = 0;
        int sum = 0;
        for (int r = l; r < nums.size(); r++) {
            sum += nums[r];
            while (sum >= target) {
                ans = min(ans, r - l + 1);
                sum -= nums[l];
                l++;
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

子数组个数

1. 越短越合法:一般要写ans += right - left + 1
2. 越长越合法:一般要写 ans += left
3. 恰好型滑动窗口:例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：

• 计算有多少个元素和 ≥k 的子数组
• 计算有多少个元素和 >k，也就是 ≥k+1 的子数组

答案就是元素和 ≥k 的子数组个数，减去元素和 ≥k+1 的子数组个数。