Partage de technologie

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

1. Préfixes et techniques

(1) Somme du préfixe

La technique de la somme des préfixes convient pour calculer rapidement et fréquemment la somme des éléments dans une plage d'index.

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) Somme de préfixe + table de hachage

Le tableau de somme de préfixes vous aide à calculer rapidement la somme des éléments d'un sous-tableau, mais que se passe-t-il si on vous demande de trouver un sous-tableau qui remplit les conditions ?Par exemple, laissez-vousnumsÀ la recherche de l'harmonie danstarget sous-tableau, même avec l'aide de préfixes et de tableaux, vous devez toujours écrire une boucle for imbriquée.Mais nous pouvons utiliser une table de hachage pour enregistrer chaque préfixe et index correspondant, afin de pouvoir calculer rapidement la somme cible commetargetsous-tableau de

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;
 
    }
};