पायथन का उपयोग करके लक्ष्य योग वाले दो गैर-ओवरलैपिंग सबएरे खोजने का प्रोग्राम

मान लीजिए हमारे पास arr नामक एक सरणी और दूसरा मान target है। हमें arr के दो गैर-ओवरलैपिंग सबएरे ढूंढने हैं जहां प्रत्येक का योग target के बराबर हो। यदि कई उत्तर हैं, तो हमें वह उत्तर ढूंढना है जहां दोनों सबएरे की लंबाई का योग सबसे छोटा हो। हमें दोनों आवश्यक सबएरे की लंबाई का न्यूनतम योग ढूंढना है, यदि ऐसा कोई सबएरे नहीं है तो -1 वापस करें।

उदाहरण के लिए, यदि इनपुट arr = [5,2,6,3,2,5] target = 5 है, तो आउटपुट 2 होगा क्योंकि योग 5 वाले तीन सबएरे हैं, वे [5], [3,2] और [5] हैं, अब उनमें से केवल दो का आकार सबसे छोटा है।

हल करने के चरण

ans := अनंत
best := एक सरणी बनाएं जिसका आकार arr के समान हो और अनंत से भरें
prefix := 0
latest := एक मैप जहां कुंजी 0 के लिए -1 संग्रहीत करें
arr के प्रत्येक इंडेक्स i और मान x के लिए, करें
- prefix := prefix + x
- यदि (prefix - target), latest में मौजूद है, तो
  - ii := latest[prefix - target]
  - यदि ii >= 0, तो
    - ans := ans और (i - ii + best[ii]) का न्यूनतम
  - best[i] := i - ii
- यदि i शून्येतर है, तो
  - latest[prefix] := i
यदि ans < 999999 तो ans वापस करें अन्यथा -1

उदाहरण

def solve(arr, target):
    ans = 999999
    best = [999999] * len(arr)
    prefix = 0
    latest = {0: -1}
    for i, x in enumerate(arr):
        prefix += x
        if prefix - target in latest:
            ii = latest[prefix - target]
            if ii >= 0:
                ans = min(ans, i - ii + best[ii])
            best[i] = i - ii
        if i:
            best[i] = min(best[i-1], best[i])
        latest[prefix] = i
    return ans if ans < 999999 else -1

arr = [5,2,6,3,2,5]
target = 5
print(solve(arr, target))

इनपुट

[5,2,6,3,2,5], 5