โปรแกรมค้นหาจำนวนสูงสุดของอาร์เรย์ย่อยที่ไม่ทับซ้อนกันโดยมีผลรวมเท่ากับเป้าหมายโดยใช้ Python

สมมติว่าเรามีจำนวนอาร์เรย์และค่าอื่นที่เรียกว่าเป้าหมาย ตอนนี้ เราต้องค้นหาจำนวนสูงสุดของอาร์เรย์ย่อยที่ไม่ซ้อนทับกันที่ไม่ว่างเปล่า เพื่อให้ผลรวมของค่าในแต่ละอาร์เรย์ย่อยที่แตกต่างกันนั้นเท่ากับเป้าหมาย

ดังนั้น หากอินพุตเท่ากับ nums =[3,2,4,5,2,1,5] เป้าหมาย =6 เอาต์พุตจะเป็น 2 เนื่องจากมีอาร์เรย์ย่อยสองชุด [2,4] และ [1,5] ซึ่งผลรวมเท่ากับ 6.

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

• t :=ชุดใหม่ที่มีองค์ประกอบเดียว 0

• อุณหภูมิ :=0

• ตอบ:=0

• สำหรับแต่ละ i ใน nums ทำ

  • อุณหภูมิ :=อุณหภูมิ + ผม

  • ก่อนหน้า :=อุณหภูมิ - เป้าหมาย

  • ถ้าก่อนหน้าอยู่ใน t แล้ว

    • ans :=ans + 1

    • t :=ชุดใหม่ที่มีอุณหภูมิองค์ประกอบเดียว

  • มิฉะนั้น

    • ใส่อุณหภูมิลงใน t

• กลับมาอีกครั้ง

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

ตัวอย่าง

def solve(nums, target):
   t = set([0])
   temp = 0
   ans=0
   for i in nums:
      temp += i
      prev = temp-target
      if prev in t:
         ans += 1
         t = set([temp])
      else:
         t.add(temp)
   return ans
nums = [3,2,4,5,2,1,5]
target = 6
print(solve(nums, target))

อินพุต

"poput","vwput",9

ผลลัพธ์

2