ধরুন আমাদের অঋণাত্মক সংখ্যার একটি তালিকা এবং একটি টার্গেট পূর্ণসংখ্যা k আছে, আমাদের একটি ফাংশন লিখতে হবে যাতে অ্যারেতে কমপক্ষে ২ আকারের একটি সন্তান সাবঅ্যারে আছে কিনা যেটির যোগফল k-এর গুণিতক, অর্থাৎ n*k যেখানে n একটি পূর্ণসংখ্যা। তাই যদি ইনপুট হয় [23,2,4,6,7], এবং k = 6, তবে ফলাফল হবে True, কারণ [2,4] একটি সন্তান সাবঅ্যারে আকার ২ যার যোগফল 6।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- একটি ম্যাপ m তৈরি করুন, m[0] := -1 এবং sum := 0, n := nums অ্যারেতে আকার সেট করুন
- i = 0 থেকে n – ১ পর্যন্ত
- 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; } }; main(){ vector<int> v = {23,2,4,6,7}; Solution ob; cout << (ob.checkSubarraySum(v, 6)); }ইনপুট
[23,2,4,6,7] 6
আউটপুট
1
