โปรแกรมค้นหารายการย่อยที่มีขนาดอย่างน้อย 2 ซึ่งมีผลรวมเป็นทวีคูณของ k ใน Python

สมมติว่าเรามีรายการตัวเลขที่ไม่เป็นลบที่เรียกว่า nums และค่าบวกอีกค่าหนึ่งคือ k เราต้องหาเช็คว่ามีรายการย่อยที่มีความยาวอย่างน้อย 2 รายการที่ผลรวมเป็นทวีคูณของ k หรือไม่

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[12, 6, 3, 4] k =5 ผลลัพธ์จะเป็น True เนื่องจากรายการย่อยคือ [12, 3] ผลรวมเป็น 15 ซึ่งหารด้วย 5 ลงตัว

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

• ผลรวม :=0
• m :=แผนที่ใหม่
• m[0] :=-1
• สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
  • sum :=sum + nums[i]
  • sum :=sum mod k
  • ถ้าผลรวมเป็น m แล้ว
    • ถ้า i - m[sum]>=2 แล้ว
      • คืนค่า True
  • มิฉะนั้น
    • m[sum] :=i
• คืนค่าเท็จ

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

ตัวอย่าง

class Solution:
   def solve(self, nums, k):
      sum = 0
      m = {}
      m[0] = -1
      for i in range(0, len(nums)):
         sum += nums[i]
         sum %= k
         if sum in m:
            if i - m[sum] >= 2:
               return True
         else:
            m[sum] = i
      return False
ob = Solution()
nums = [12, 6, 3, 4]
k = 5
print(ob.solve(nums, k))

อินพุต

[12, 6, 3, 4], 5

ผลลัพธ์

True