C++ में सतत उपसरणी योग

मान लीजिए हमारे पास गैर-ऋणात्मक संख्याओं की एक सूची और एक लक्ष्य पूर्णांक k है, हमें एक फ़ंक्शन लिखना है जो जांचता है कि क्या सरणी में कम से कम आकार 2 की एक सतत उपसरणी है जो k के गुणक तक जुड़ती है, n*k तक जुड़ती है जहां n भी एक पूर्णांक है। इसलिए यदि इनपुट [23,2,4,6,7] है, और k = 6, तो परिणाम True होगा, क्योंकि [2,4] आकार 2 की एक सतत उपसरणी है और 6 तक जुड़ती है।

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• एक मैप m बनाएं, m[0] := -1 और sum := 0, n := nums सरणी का आकार सेट करें
• i = 0 से n-1 तक:
  • sum := sum + nums[i]
  • यदि k शून्येतर है, तो sum := sum mod k
  • यदि m में sum है, और i - m[sum] >= 2, तो true लौटाएं
  • यदि m में sum नहीं है, तो m[sum] := i सेट करें
• false लौटाएं

उदाहरण

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

class Solution { 
public: 
    bool checkSubarraySum(vector<int>& nums, int k) { 
        unordered_map<int, int> m; 
        m[0] = -1; 
        int sum = 0; 
        int n = nums.size(); 
        for(int i = 0; i < n; i++){ 
            sum += nums[i]; 
            if(k) 
                sum %= k; 
            if(m.count(sum) && i - m[sum] >= 2){ 
                return true; 
            } 
            if(!m.count(sum)) m[sum] = i; 
        } 
        return false; 
    } 
}; 

int main(){ 
    vector<int> v = {23,2,4,6,7}; 
    Solution ob; 
    cout << (ob.checkSubarraySum(v, 6)); 
}

इनपुट

[23,2,4,6,7] 6

आउटपुट

1