ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা রয়েছে এবং লক্ষ্য বলে আরেকটি ইনপুট আছে, আমাদেরকে সবচেয়ে ছোট সাবলিস্টের আকার খুঁজে বের করতে হবে যাতে এর সমষ্টির মান লক্ষ্যের সমান বা বড় হয়। যদি এমন কোন সাবলিস্ট না থাকে তাহলে -1 রিটার্ন করুন।
সুতরাং, যদি ইনপুটটি nums =[2, 11, -4, 17, 4] টার্গেট =19 এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমরা কমপক্ষে 19 এর যোগফল পেতে [17, 4] নির্বাচন করতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ps :=শুধুমাত্র একটি উপাদান 0
সহ একটি তালিকা -
প্রতিটি সংখ্যার জন্য, করুন
-
ps
এর পরে সন্নিবেশ করুন (ps + num-এর শেষ উপাদান) -
যদি num>=টার্গেট হয়, তাহলে
-
রিটার্ন 1
-
-
-
min_size :=inf
-
q :=[0]
-
j :=0
-
আমি রেঞ্জ 1 থেকে ps আকারের জন্য, করুন
-
j :=ন্যূনতম j, q এর আকার - 1
-
যখন j
=লক্ষ্য, কর
-
min_size :=সর্বনিম্ন_size এবং (i - q[j])
-
j :=j + 1
-
-
যখন q এবং ps[i] <=ps[q এর শেষ উপাদান], do
-
q
থেকে শেষ উপাদান মুছুন
-
-
q
এর শেষে i ঢোকান
-
-
-
min_size যদি min_size
রিটার্ন করুন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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
আউটপুট
2
