পাইথনে দুটি নন-ওভারল্যাপিং সাবলিস্ট যাদের যোগফল k এবং দৈর্ঘ্যের যোগফল ন্যূনতম

দেওয়া লিস্ট nums এবং টার্গেট k। দুটি নন-ওভারল্যাপিং সাবলিস্ট খুঁজতে হবে যাদের প্রতিটির যোগফল k, এবং তাদের দৈর্ঘ্যের যোগফল ন্যূনতম হবে। না পেলে -1 রিটার্ন।

উদাহরণ: nums = [7, 10, -2, -1, 4, 3], k=7 → সাবলিস্ট [7] (দৈর্ঘ্য ১) এবং [4,3] (দৈর্ঘ্য ২) → আউটপুট 3।

প্রিফিক্স-সাফিক্স + হ্যাশম্যাপ সমাধান

1. প্রিফিক্স অ্যারের তৈরি: বাম থেকে ডানে যাওয়ায় প্রতিটি ইনডেক্স i-তে শেষ হওয়া সাবলিস্ট যার সম k, তার ন্যূনতম দৈর্ঘ্য স্টোর করুন। prefix[i] = ইনডেক্স i পর্যন্ত ন্যূনতম দৈর্ঘ্য।
2. সাফিক্স অ্যারের তৈরি: ডান থেকে বামে যাওয়ায় প্রতিটি ইনডেক্স i-তে শুরু হওয়া সাবলিস্ট যার সম k, তার ন্যূনতম দৈর্ঘ্য স্টোর করুন। suffix[i] = ইনডেক্স i থেকে শুরু হয়ে ন্যূনতম দৈর্ঘ্য।
3. ফলাফল: min(prefix[i] + suffix[i+1]) for all i।

পাইথন কোড

class Solution:
    def solve(self, A, target):
        INF = float("inf")
        N = len(A)
        
        # Prefix: left to right
        prefix = [INF] * N
        last = {0: -1}
        s = 0
        for i in range(N):
            s += A[i]
            prefix[i] = i - last.get(s - target, -INF)
            last[s] = i
        for i in range(1, N):
            prefix[i] = min(prefix[i], prefix[i-1])
        
        # Suffix: right to left
        suffix = [INF] * N
        last = {0: N}
        s = 0
        for i in range(N-1, -1, -1):
            s += A[i]
            suffix[i] = last.get(s - target, INF) - i
            last[s] = i
        for i in range(N-2, -1, -1):
            suffix[i] = min(suffix[i], suffix[i+1])
        
        ans = min(prefix[i] + suffix[i+1] for i in range(N-1))
        return ans if ans < INF else -1

ob = Solution()
print(ob.solve([7, 10, -2, -1, 4, 3], 7))  # 3

টাইম কমপ্লেক্সিটি: O(n), স্পেস: O(n)।