C++-এ Maximum Size Subarray Sum Equals k: লক্ষ্য সমান সাবঅ্যারের সর্বোচ্চ দৈর্ঘ্য

একটি অ্যারে nums এবং একটি টার্গেট ভ্যালু k দেওয়া আছে। যোগফল k হওয়া সাবঅ্যারের মধ্যে সর্বোচ্চ দৈর্ঘ্যের वाला বের করতে হবে। যদি এমন কোনো সাবঅ্যারে না থাকে, তবে 0 রিটার্ন করুন।

উদাহরণ

ইনপুট: nums = [1, -1, 5, -2, 3], k = 3

আউটপুট: 4

ব্যাখ্যা: সাবঅ্যারে [1, -1, 5, -2] এর যোগফল ৩ এবং দৈর্ঘ্য ৪ (সর্বোচ্চ)।

সমাধানের পদ্ধতি (Prefix Sum + Hash Map)

ret = 0, একটি হ্যাশ ম্যাপ m (প্রিফিক্স সাম -> ইনডেক্স) ঘোষণা করুন।
m[0] = -1 সেট করুন (খালি প্রিফিক্স)।
temp = 0 (রানিং প্রিফিক্স সাম)।
i = 0 থেকে n-1 পর্যন্ত লুপ:
- temp += nums[i]।
- যদি (temp - k) ম্যাপে থাকে, তবে সাবঅ্যারে পাওয়া গেল। দৈর্ঘ্য = i - m[temp - k]। ret = max(ret, দৈর্ঘ্য) আপডেট করুন।
- যদি temp ম্যাপে না থাকে, তবে m[temp] = i সেট করুন (শুধু প্রথম OCurrence রাখি)।
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