पायथन में लक्ष्य से कम या बराबर योग वाली सबसे छोटी सबलिस्ट का आकार ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, और एक अन्य इनपुट target है, हमें सबसे छोटी सबलिस्ट का आकार ज्ञात करना है जिसका योग मान target के समान या बड़ा हो। यदि ऐसी कोई सबलिस्ट नहीं है तो -1 लौटाएं।

इसलिए, यदि इनपुट nums = [2, 11, -4, 17, 4] target = 19 जैसा है, तो आउटपुट 2 होगा, क्योंकि हम [17, 4] चुनकर कम से कम 19 का योग प्राप्त कर सकते हैं।

हल करने के चरण

ps := केवल एक तत्व 0 वाली सूची
nums में प्रत्येक num के लिए, करें
- (ps के अंतिम तत्व + num) को ps के बाद डालें
- यदि num >= target, तो 1 लौटाएं
min_size := infinity
q := [0]
j := 0
i के लिए 1 से ps के आकार तक की रेंज में, करें
- j := j और q के आकार - 1 का न्यूनतम
  - जब तक j < q का आकार और ps[i] - ps[q[j]] >= target, करें
    - min_size := min_size और (i - q[j]) का न्यूनतम
    - j := j + 1
  - जब तक q और ps[i] <= ps[q का अंतिम तत्व], करें q का अंतिम तत्व हटाएं
  - i को q के अंत में डालें
यदि min_size < infinity तो min_size लौटाएं अन्यथा -1

उदाहरण

class Solution:
    def solve(self, nums, target):
        ps = [0]
        for num in nums:
            ps += [ps[-1] + num]
            if num >= target:
                return 1
        min_size = float("inf")
        q = [0]
        j = 0
        for i in range(1, len(ps)):
            j = min(j, len(q) - 1)
            while j < len(q) and ps[i] - ps[q[j]] >= target:
                min_size = min(min_size, i - q[j])
                j += 1
            while q and ps[i] <= ps[q[-1]]:
                q.pop()
            q.append(i)
        return min_size if min_size < float("inf") else -1

ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))

इनपुट

[2, 11, -4, 17, 4], 19