โปรแกรมหาสับลิสต์ขนาด ≥2 ที่ผลรวมหาร k ลงตัวใน Python

สมมติว่ามีรายการตัวเลขไม่ติดลบ nums และ k > 0 ต้องการตรวจสอบว่ามี subarray ความยาว ≥ 2 ที่ผลรวมหาร k ลงตัวหรือไม่

ตัวอย่าง: nums = [12,6,3,4], k=5 ผลลัพธ์ True subarray [12,3] ผลรวม 15 หาร 5 ลงตัว

ขั้นตอนการแก้ปัญหา

1. sum = 0, m = {0: -1}
2. วน i จาก 0 ถึง len(nums)-1:
   • sum = (sum + nums[i]) % k
   • ถ้า sum in m และ i - m[sum] >= 2: คืน True
   • มิฉะนั้น m[sum] = i
3. คืน False

ตัวอย่างโค้ด

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