C++ में अधिकतम आकार सबएरे योग बराबर K - प्रीफिक्स योग + हैश मैप

समस्या विवरण

मान लीजिए हमारे पास nums नामक एक सरणी है और एक लक्ष्य मान k है, हमें उस सबएरे की अधिकतम लंबाई ढूंढनी है जिसका योग k के बराबर है। यदि कोई मौजूद नहीं है, तो 0 लौटाएं।

उदाहरण के लिए, यदि इनपुट nums = [1, -1, 5, -2, 3], k = 3 है, तो आउटपुट 4 होगा, क्योंकि सबएरे [1, -1, 5, -2] का योग 3 है और यह सबसे लंबा है।

समाधान दृष्टिकोण

प्रीफिक्स योग + हैश मैप का उपयोग करके O(n) समय में:

1. ret := 0
2. एक मैप m परिभाषित करें - प्रीफिक्स योग को सूचकांक पर मैप करने के लिए
3. n := nums का आकार
4. temp := 0, m[0] := -1
5. i को 0 से n-1 तक लूप करें:
   • temp := temp + nums[i]
   • यदि (temp - k) m में है, तो ret = max(ret, i - m[temp - k]) अपडेट करें
   • यदि temp m में नहीं है, तो m[temp] := i
6. ret लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int maxSubArrayLen(vector<int>& nums, int k) { 
        int ret = 0; 
        unordered_map <int, int> m; 
        int n = nums.size(); 
        int temp = 0; 
        m[0] = -1; 
        for(int i = 0; i < n; i++){ 
            temp += nums[i]; 
            if(m.count(temp - k)){ 
                ret = max(ret, i - m[temp - k]); 
            } 
            if(!m.count(temp)){ 
                m[temp] = i; 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {1,-1,5,-2,3}; 
    cout << (ob.maxSubArrayLen(v, 3)); 
    return 0;
}

इनपुट

[1,-1,5,-2,3], 3

आउटपुट

4