构建前缀信息解决子数组问题

构建前缀信息解决子数组问题

303. 区域和检索 - 数组不可变

#include <vector>

using namespace std;

class NumArray {
public:
    // 前缀和数组
    vector<int> prefixSum;

    NumArray(vector<int> &nums) {
        prefixSum.resize(nums.size() + 1);
        prefixSum[0] = 0;
        for (int i = 0; i < nums.size(); ++i)
            prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
};

未排序数组中累加和为给定值的最长子数组长度

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i)
        cin >> nums[i];

    // 记录前缀和最早出现的位置，这样才能使子数组更大
    unordered_map<int, int> map;
    // 前缀和 0 首次出现在下标 -1 的位置
    map.emplace(0, -1);
    int prefixSum = 0;
    int res = 0;

    for (int i = 0; i < n; ++i) {
        prefixSum += nums[i];
        // 只记录第一次出现的位置
        if (map.find(prefixSum) == map.end())
            map[prefixSum] = i;
        // 之前的某个位置到当前位置构成的子数组，和为 k
        if (map.find(prefixSum - k) != map.end())
            res = max(res, i - map[prefixSum - k]);
    }
    cout << res;
}

560. 和为 K 的子数组

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int subarraySum(vector<int> &nums, int k) {
        // 记录前缀和出现的次数
        unordered_map<int, int> map;
        map.emplace(0, 1);
        int res = 0;
        int prefixSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            prefixSum += nums[i];
            // 和为 k 的子数组个数
            if (map.find(prefixSum - k) != map.end())
                res += map[prefixSum - k];
            map[prefixSum]++;
        }
        return res;
    }
};

未排序数组中累加和为给定值的最长子数组系列问题补1

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i)
        cin >> nums[i];

    // 记录正数负数个数的差值的最早出现位置
    unordered_map<int, int> map;
    map.emplace(0, -1);
    // 正数负数个数的差值
    int prefix = 0;
    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] > 0) prefix++;
        if (nums[i] < 0) prefix--;
        // 之前出现过，说明那个位置到当前位置的累加和为 0
        if (map.find(prefix) != map.end())
            res = max(res, i - map[prefix]);
        // 记录最早出现位置
        if (map.find(prefix) == map.end())
            map.emplace(prefix, i);
    }
    cout << res;
}

1124. 表现良好的最长时间段

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int longestWPI(vector<int> &hours) {
        // 某个前缀和，最早出现的位置
        unordered_map<int, int> map;
        map.emplace(0, -1);
        // 记录前缀中大于 8h 的天数和小于等于 8h 的天数之差
        int prefix = 0;
        int res = 0;

        for (int i = 0; i < hours.size(); i++) {
            prefix += hours[i] > 8 ? 1 : -1;
            if (prefix > 0) {
                // 说明从数组开头到当前位置就是表现良好的时间段
                res = i + 1;
            } else {
                // 若当前 prefix 为 -3，则找 -4 是否已经出现，若出现，则说明 -4 出现的位置到当前位置的子数组是符合条件的（大于8h的天数严格大于一半）
                // 若之前还有 -5、-6 啥的，其之前一定出现过 -4，因为是从 0 开始加一减一的，先出现 -4 才可能出现 -5、-6
                if (map.find(prefix - 1) != map.end())
                    res = max(res, i - map[prefix - 1]);
            }
            // 只记录第一次出现的位置
            if (map.find(prefix) == map.end())
                map.emplace(prefix, i);
        }
        return res;
    }
};

1590. 使数组和能被 P 整除

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int minSubarray(vector<int> &nums, int p) {
        // 总体和模 p 的余数，也是需要删除的部分的累加和模 p 的余数
        int remove = 0;
        for (int num: nums) remove = (remove + num) % p;
        // 不需要移除子数组
        if (remove == 0) return 0;

        int res = INT_MAX;
        // 记录累加和
        int prefixSum = 0;
        // key 为模 p 的余数，value 为该值最后一次出现的位置
        unordered_map<int, int> map;
        map.emplace(0, -1);
        for (int i = 0; i < nums.size(); i++) {
            prefixSum = (prefixSum + nums[i]) % p;
            // 当前位置的前缀和模 p 的值为 prefixSum，整体数组累加和模 p 的值为 remove
            // 需要删除子数组的累加和模 p 的值为 remove，这样删除元素后的整体数组模 p 的值才能为 0，才能被 p 整除
            // 所以要往前寻找累加和模 p 的值为 find 最后一次出现的位置，才能使删除的数组长度最小
            int find = (prefixSum - remove + p) % p;
            if (map.find(find) != map.end())
                res = min(res, i - map[find]);
            // 记录 prefixSum 最后一次出现的位置
            map[prefixSum] = i;
        }
        // 没得删或者要全删时返回 -1
        return (res == INT_MAX || res == nums.size()) ? -1 : res;
    }
};

1371. 每个元音包含偶数次的最长子字符串

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int ans = 0;
        int len = s.length();
        // 只有 5 个元音字符，状态 5 位，状态总数 32 种，-2 表示这个状态之前没出现过
        vector<int> map(32, -2);
        // aeiou 00000
        map[0] = -1;
        // status 低 5 位从低到高分表表示 aeiou 的奇偶性，0 为偶，1 为奇
        int status = 0;

        for (int i = 0, m; i < len; i++) {
            // 当前字符 在 status 中对应的位置
            m = move(s[i]);
            // 情况1 : 当前字符不是元音，status 不变
            // 情况2 : 当前字符是元音，a~u(0~4)，修改相应的状态，亦或运算改变对应元音字符的奇偶性
            if (m != -1) status ^= 1 << m;
            if (map[status] != -2) {
                // 同样的状态，之前最早出现在哪
                ans = max(ans, i - map[status]);
            } else {
                // 记录状态第一次出现的位置
                map[status] = i;
            }
        }
        return ans;
    }

    int move(char ch) {
        switch (ch) {
            case 'a':
                return 0;
            case 'e':
                return 1;
            case 'i':
                return 2;
            case 'o':
                return 3;
            case 'u':
                return 4;
            default:
                // 不是元音
                return -1;
        }
    }
};