मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान k है, हमें nums में दो नॉन-ओवरलैपिंग सबलिस्ट ढूंढनी हैं जिनका योग k है, और हमें उनकी लंबाई का योग ढूंढना है। जब दो से अधिक संभावित सबलिस्ट हों, तो हमें दो सबसे छोटी सबलिस्ट की लंबाई का योग ढूंढना होगा। यदि हम उत्तर नहीं ढूंढ सकते, तो -1 लौटाएं।
तो, यदि इनपुट nums = [7, 10, -2, -1, 4, 3], k = 7 जैसा है, तो आउटपुट 3 होगा, क्योंकि हम [7] और [4, 3] जैसी सबलिस्ट चुनते हैं। हमने [10, -2, -1] को नहीं चुना क्योंकि यह लंबा है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- N := A का आकार
- prefix := आकार N का, अनंत से भरें
- last := मान -1 के साथ कुंजी 0 का मैप {0: -1}
- s := 0
- i को 0 से N तक की रेंज में लिए, करें
- s := s + A[i]
- prefix[i] := i - last[s - target], यदि नहीं मिला तो -अनंत सेट करें
- last[s] := i
- i को 1 से N तक की रेंज में लिए, करें
- prefix[i] := prefix[i] और prefix[i-1] का न्यूनतम
- suffix := आकार N का, अनंत से भरें
- last := मान N के साथ कुंजी 0 का मैप {0: N}
- s := 0
- i को N-1 से -1 तक घटाते हुए, करें
- s := s + A[i]
- suffix[i] := last[s - target] (यदि नहीं मिला तो अनंत सेट करें) - i
- last[s] := i
- i को N-2 से -1 तक घटाते हुए, करें
- suffix[i] := suffix[i] और suffix[i+1] का न्यूनतम
- ans := प्रत्येक i के लिए prefix[i] + suffix[i+1] का न्यूनतम, रेंज 0 से N-1
- ans लौटाएं यदि ans < अनंत अन्यथा -1
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, A, target):
INF = float("inf")
N = len(A)
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 = [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()
nums = [7, 10, -2, -1, 4, 3]
k = 7
print(ob.solve(nums, k))
इनपुट
[7, 10, -2, -1, 4, 3], 7आउटपुट
3
