167. 两数之和 II - 输入有序数组

采用方向相反的两个指针来扫遍数组，计算两个元素和:

• 如果大于target，右指针左移
• 小于target，左指针右移
• 如果等于的话，返回二者的下标+1

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            if (numbers[right] + numbers[left] > target) {
                right--;
            } else if (numbers[right] + numbers[left] < target) {
                left++;
            } else {
                return {left + 1, right + 1};
            }
        }
        return {}; // 没找到
    }
};

825. 适龄的朋友

排序＋双指针

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        // 排序 + 双指针
        sort(ages.begin(), ages.end());
        int left = 0, right = 0, res = 0, n = ages.size();
        // 寻找ages可以发送好友请求的范围
        for (auto age: ages) {
            if (age < 15) {
                continue;
            }
            // left指向第一个满足的元素
            while (left + 1 < n && ages[left] <= 0.5 * age + 7) left++;
            // right指向最后一个满足的元素
            while (right + 1 < n && ages[right + 1] <= age) right++;
            res += right - left; // 这里不用加一，因为本身也在这个区间内，要将其排除
        }

        return res;
    }
};

计数排序+前缀和

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> cnt(121), pre(121); // 用于计数排序和计算前缀和
        for (auto age: ages) {
            cnt[age]++;
        }
        // 计算前缀和
        for (int i = 1; i < 121; i++) {
            pre[i] = pre[i - 1] + cnt[i];
        }
        int res = 0;
        for (int i = 15; i < 121; i++) {
            if (cnt[i]) {
                int bound = 0.5 * i + 8; // 界向下取整
                res += cnt[i] * (pre[i] - pre[bound - 1] - 1);
            }
        }
        return res;
    }
};

443. 压缩字符串

结果要求返回int，但是得修改原数组，真滴恶心

额外空间

class Solution {
public:
    int compress(vector<char>& chars) {
        if (chars.size() <= 1) return chars.size();
        string res;
        int cnt= 1;
        int i;
        for (i = 1; i < chars.size(); i++) {
            if (chars[i] != chars[i - 1]) {
                res.push_back(chars[i - 1]);
                if (cnt > 1) {
                    res += to_string(cnt);
                    cnt = 1;
                }
            } else {
                cnt++;
            }
        }
        res.push_back(chars[i - 1]);
        if (cnt > 1) {
            res += to_string(cnt);
        }

        for (int i = 0; i < res.size(); i++) {
            chars[i] = res[i];
        }

        return res.size();
    }
};

双指针（快慢/读写双指针）

读写双指针，一个指针往前扫描，查找连续相等的字符的最后一个，写指针记录长度

class Solution {
public:
    int compress(vector<char>& chars) {
        if (chars.size() <= 1) return chars.size();
        int l = 0, n = chars.size(), idx = 0;
        for (int r = 0; r < n; r++) {
            if (r == n - 1 || chars[r] != chars[r + 1]) { // r是临界点
                chars[idx++] = chars[r];
                int len = r - l + 1;
                if (len > 1) {
                    string s = to_string(r - l + 1); // 先转化为字符串，再逐个拷贝
                    for (auto& ch : s) chars[idx++] = ch;
                }
                l = r + 1;
            }
        }
        // 关于字母后面的数字，也可以通过不断取余除以10的办法，添加到chars中，但是添加完毕要翻转一下
        return idx;
    }
};