ตรวจสอบว่าแบ่ง Array เป็น K Subarray ต่อเนื่องที่ Sum เท่ากันได้หรือไม่ด้วย Python

สมมติมี Array nums และค่า K ต้องตรวจสอบว่าแบ่ง nums เป็น K Subarray ต่อเนื่องที่ Sum เท่ากันได้หรือไม่

เช่น Input nums = [2, 5, 3, 4, 7], k = 3 Output True เพราะ [(2,5), (3,4), (7)] Sum = 7 ทุกคู่

ขั้นตอนแก้:

• คำนวณ Cumulative Sum
• Total Sum ต้องหาร K ลงตัว
• Target = Total Sum / K
• วนหา Partition Points โดยเช็ค Cumulative Sum Diff

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

def solve(nums, k):
    n = len(nums)
    cumul_sum = [0 for i in range(n)]
    cumul_sum[0] = nums[0]
    for i in range(1, n):
        cumul_sum[i] = cumul_sum[i - 1] + nums[i]
    total_sum = cumul_sum[n - 1]
    if total_sum % k != 0:
        return False
    count = 0
    pos = -1
    for i in range(n):
        if pos == -1:
            sub = 0
        else:
            sub = cumul_sum[pos]
        if cumul_sum[i] - sub == total_sum / k:
            pos = i
            count += 1
        elif cumul_sum[i] - cumul_sum[pos] > total_sum / k:
            break
    return count == k

nums = [2, 5, 3, 4, 7]
k = 3
print(solve(nums, k))

Input

[2, 5, 3, 4, 7], 3

Output

True