โปรแกรมหาผลรวมของความยาวของรายการย่อยที่ไม่ทับซ้อนกันสองรายการซึ่งให้ผลรวมในPython

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหารายการย่อยที่ไม่ทับซ้อนกันสองรายการใน num ซึ่งมีผลรวมเป็น k และเราต้องหาผลรวมของความยาว เมื่อมีรายการย่อยที่เป็นไปได้มากกว่าสองรายการ เราต้องหาผลรวมของความยาวของรายการย่อยที่เล็กที่สุดสองรายการ หากเราหาคำตอบไม่ได้ ให้คืนค่า -1

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[7, 10, −2, −1, 4, 3] k =7 ผลลัพธ์จะเป็น 3 ในขณะที่เราเลือกรายการย่อยเช่น [7] และ [4, 3] . เราไม่ได้เลือก [10, −2, −1] เพราะมันยาวกว่า

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=ขนาด A

• คำนำหน้า :=ของขนาด N และเติมอินฟินิตี้

• สุดท้าย :=แผนที่ที่มีค่า -1 สำหรับคีย์ 0 {0:-1}

• s :=0

• สำหรับผมอยู่ในช่วง 0 ถึง N ทำ

  • s :=s + A[i]

  • คำนำหน้า[i] :=i − Last[s − target] หากไม่พบ set −infinity

  • ล่าสุด[s] :=i

• สำหรับผมอยู่ในช่วง 1 ถึง N ทำ

  • คำนำหน้า[i] :=คำนำหน้าขั้นต่ำ[i] คำนำหน้า[i − 1]

• คำต่อท้าย :=ขนาด N และเติมอินฟินิตี้

• สุดท้าย :=แผนที่ที่มีค่า N สำหรับคีย์ 0 {0:N}

• s :=0

• สำหรับฉันอยู่ในช่วง N − 1 ถึง -1 ลดลง 1 ทำ

  • s :=s + A[i]

  • suffix[i] :=last[s − target] (หากไม่พบ set infinity) − i

  • ล่าสุด[s] :=i

• สำหรับฉันอยู่ในช่วง N − 2 ถึง -1 ลดลง 1 ทำ

  • suffix[i] :=ขั้นต่ำของ suffix[i] และ suffix[i + 1]

• ans :=ขั้นต่ำของคำนำหน้า[i] + suffix[i + 1] สำหรับแต่ละ i ในช่วง 0 ถึง N − 1

• ส่งคืน ans if ans

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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