Berbagi teknologi

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

1. Awalan dan teknik

(1) Jumlah awalan

Teknik penjumlahan awalan cocok untuk menghitung jumlah elemen dalam rentang indeks dengan cepat dan sering.

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) Jumlah awalan + tabel hash

Awalan sum array membantu Anda dengan cepat menghitung jumlah elemen subarray, namun bagaimana jika Anda diminta untuk menemukan subarray yang memenuhi ketentuan?Misalnya, izinkan AndanumsMencari harmoni dalamtarget subarray, bahkan dengan bantuan prefiks dan array, Anda masih harus menulis loop for yang bersarang.Tapi kita bisa menggunakan tabel hash untuk mencatat setiap awalan dan indeks yang sesuai, sehingga kita bisa dengan cepat menghitung jumlah targetnyatargetsubarray dari

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