C++ में Subarray Sum Equals K

मान लीजिए हमारे पास पूर्णांकों की एक सरणी और एक पूर्णांक k है, हमें उन सतत उपसरणियों (continuous subarrays) की कुल संख्या ढूंढनी है जिनका योग k के समान है। इसलिए यदि nums सरणी [1, 1, 1] है और k 2 है, तो आउटपुट 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• sums नामक एक मैप परिभाषित करें, temp := 0, sums[0] := 1 और ans := 0
• i को 0 से सरणी के आकार तक की रेंज में
  • temp := temp + n[i]
  • यदि sums में k - temp है, तो
    • ans := ans + sums[k - temp]
  • sums[-temp] के मान को 1 से बढ़ाएं
• ans लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h> using namespace std; class Solution { public:    int subarraySum(vector<int>& n, int k) {       unordered_map <int, int> sums;       int temp = 0;       sums[0] = 1;       int ans =0;       for(int i =0;i<n.size();i++){          temp+= n[i];          if(sums.find(k-temp)!=sums.end()){             ans += sums[k-temp];          }          sums[-temp]++;       }       return ans;    } }; main(){    Solution ob;    vector<int> v = {1,1,1};    cout << (ob.subarraySum(v, 2)); }

इनपुट

[1,1,1] 2

आउटपुट

2