สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอินพุตอื่นที่เรียกว่า target เราต้องหาขนาดของรายการย่อยที่สั้นที่สุดเพื่อให้ค่ารวมเท่ากับเป้าหมายหรือใหญ่กว่า หากไม่มีรายการย่อยดังกล่าว ให้คืนค่า -1
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 11, -4, 17, 4] target =19 ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถเลือก [17, 4] เพื่อให้ได้ผลรวมอย่างน้อย 19
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ps :=รายการที่มีเพียงหนึ่งองค์ประกอบ 0
-
สำหรับแต่ละ num เป็น num ทำ
-
แทรก (องค์ประกอบสุดท้ายของ ps + num) หลัง ps
-
ถ้า num>=เป้าหมาย แล้ว
-
กลับ 1
-
-
-
min_size :=inf
-
q :=[0]
-
เจ :=0
-
สำหรับฉันในช่วง 1 ถึงขนาด ps ทำ
-
j :=ขั้นต่ำของ j, ขนาด q - 1
-
ในขณะที่ j <ขนาดของ q และ ps[i] - ps[q[j]]>=เป้าหมาย ทำ
-
min_size :=ขั้นต่ำของ min_size และ (i - q[j])
-
เจ :=เจ + 1
-
-
ในขณะที่ q และ ps[i] <=ps[องค์ประกอบสุดท้ายของ q] ทำ
-
ลบองค์ประกอบสุดท้ายออกจาก q
-
-
ใส่ i ต่อท้าย q
-
-
-
คืนค่า 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
