प्रौद्योगिकी साझेदारी

한어Русский язык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 subarray, उपसर्गस्य, arrays इत्यस्य च साहाय्येन अपि, भवद्भिः अद्यापि nested for loop इति लिखितव्यम् ।परन्तु वयं प्रत्येकं उपसर्गं तत्सम्बद्धं च अनुक्रमणिकां अभिलेखयितुं hash table इत्यस्य उपयोगं कर्तुं शक्नुमः, येन वयं शीघ्रं target sum as इत्यस्य गणनां कर्तुं शक्नुमःtargetउपसरणिका of

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