Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Prefissi e tecniche

(1) Somma del prefisso

La tecnica della somma dei prefissi è adatta per calcolare rapidamente e frequentemente la somma degli elementi all'interno di un intervallo di indici.

class NumArray {
public:
    vector<int> preSum; //前缀和数组
    NumArray(vector<int>& nums) {
        //preSum[0] = 0，便于计算累加和
        preSum.resize(nums.size() + 1, 0);
        for(int i = 0; i < nums.size(); i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        // 查询闭区间 [left, right] 的累加和
        return preSum[right + 1] - preSum[left];
    }
};

(2) Somma del prefisso + tabella hash

L'array di somma dei prefissi ti aiuta a calcolare rapidamente la somma degli elementi di un sottoarray, ma cosa succede se ti viene chiesto di trovare un sottoarray che soddisfa le condizioni?Ad esempio, lascia che tunumsAlla ricerca dell'armoniatarget subarray, anche con l'aiuto di prefissi e array, devi comunque scrivere un ciclo for nidificato.Ma possiamo usare una tabella hash per registrare ogni prefisso e indice corrispondente, in modo da poter calcolare rapidamente la somma targettargetsottoarray di

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int len = 0;
        vector<int> preSum(nums.size() + 1, 0);
 
        for(int i = 0; i < nums.size(); i++)
            preSum[i+1] = preSum[i] + (nums[i] == 0 ? -1 : 1);
 
        // 前缀和到索引的映射，方便快速查找所需的前缀和
        unordered_map<int, int> umap;
 
        for(int i = 0; i < preSum.size(); i++){
            // 如果这个前缀和还没有对应的索引，说明这个前缀和第一次出现，记录下来
            if(umap.find(preSum[i]) == umap.end()) umap[preSum[i]] = i;
            else len = max(len, i - umap[preSum[i]]);
        }
        return len;
    }
};

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        vector<int>preSum(nums.size() + 1, 0);
 
        for(int i = 0; i < nums.size(); i++)
            preSum[i + 1] = preSum[i] + nums[i];
 
        unordered_map<int, int> umap;
 
        // 寻找 i, j 使得 (preSum[i] - preSum[j]) % k == 0 且 i - j >= 2
        // (preSum[i] - preSum[j]) % k == 0 其实就是 preSum[i] % k == preSum[j] % k
        for(int i = 0; i < preSum.size(); i++){
            auto it = umap.find(preSum[i] % k);
            if(it == umap.end()) umap[preSum[i] % k] = i;
            else if ((i - it->second) >=2) return true;
        }
        return false;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        vector<int> preSum(nums.size() + 1, 0);
 
        for(int i = 0; i < nums.size(); i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }
 
        // 寻找 i, j 使得 preSum[i] - preSum[j] == k, i > j
        // nums = [1,2,3], k = 3, preSum = [0,1,3,6]
        unordered_map<int, int> umap;
        for(int i = 0; i < preSum.size(); i++){
            if(umap.find(preSum[i] - k) != umap.end()) ans += umap[preSum[i] - k]; // 该语句必须放在前面
            
            if(umap.find(preSum[i]) == umap.end()) umap[preSum[i]] = 1;
            else umap[preSum[i]]++;
        }
        return ans;
 
    }
};