प्रीफिक्स सम और सेट का उपयोग करके टारगेट सम वाले नॉन-ओवरलैपिंग सबअर्रे की मैक्सिमम संख्या ढूंढें (ग्रीडी)।
एल्गोरिदम
tसेट में प्रीफिक्स सम स्टोर करें (शुरू में {0})।temp= करंट प्रीफिक्स सम।- प्रत्येक एलिमेंट के लिए:
temp += i,prev = temp - target। - अगर
prev in t: सबअर्रे मिला,ans++,t = {temp}रीसेट करें (नॉन-ओवरलैपिंग)। - अन्यथा
t.add(temp)।
उदाहरण कोड
def solve(nums, target):
t = set([0])
temp = 0
ans = 0
for i in nums:
temp += i
prev = temp - target
if prev in t:
ans += 1
t = set([temp])
else:
t.add(temp)
return ans
# टेस्ट: nums=[3,2,4,5,2,1,5], target=6 -> सबअर्रे [2,4] और [1,5] -> आउटपुट: 2
इनपुट/आउटपुट
इनपुट: nums=[3,2,4,5,2,1,5], target=6
आउटपुट: 2
