Κοινή χρήση τεχνολογίας

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

1. Προθέματα και τεχνικές

(1) Άθροισμα προθέματος

Η τεχνική άθροισης προθέματος είναι κατάλληλη για τον γρήγορο και συχνό υπολογισμό του αθροίσματος των στοιχείων εντός μιας περιοχής ευρετηρίου.

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) Πρόθεμα άθροισμα + πίνακας κατακερματισμού

Ο πίνακας αθροίσματος προθέματος σάς βοηθά να υπολογίσετε γρήγορα το άθροισμα των στοιχείων ενός υποπίνακα, αλλά τι γίνεται αν σας ζητηθεί να βρείτε έναν υποπίνακα που πληροί τις προϋποθέσεις;Για παράδειγμα, αφήστε σαςnumsΑναζητώντας την αρμονία μέσαtarget υποπίνακας, ακόμη και με τη βοήθεια προθεμάτων και πινάκων, πρέπει να γράψετε έναν ένθετο βρόχο για.Μπορούμε όμως να χρησιμοποιήσουμε έναν πίνακα κατακερματισμού για να καταγράψουμε κάθε πρόθεμα και το αντίστοιχο ευρετήριο, έτσι ώστε να μπορούμε να υπολογίσουμε γρήγορα το άθροισμα στόχο ωςtargetυποσυστοιχία των

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