โปรแกรมหาผลรวมความยาว Subarray 2 ชุดไม่ทับซ้อน ที่ผลรวมเท่ากับ k (Python)

ปัญหา

กำหนด list nums และค่า k หา subarray 2 ชุดที่ไม่ทับซ้อน (non-overlapping) ซึ่งแต่ละชุดมีผลรวม = k
คืนค่า "ผลรวมความยาว" ของทั้งสองชุด ที่น้อยที่สุด ถ้าไม่มี → -1

ตัวอย่าง: nums=[7,10,-2,-1,4,3], k=7 → 3
เลือก [7] (len=1) และ [4,3] (len=2) รวม = 3
ไม่เลือก [10,-2,-1] (len=3) เพราะยาวกว่า

วิธีแก้: Prefix + Suffix Minimum Lengths

คำนวณความยาว subarray สั้นที่สุดที่ sum=k สำหรับ prefix และ suffix แล้วรวม

อัลกอริทึม

1. Prefix pass (ซ้าย→ขวา): หา min length subarray sum=k จบที่หรือก่อน i
   • ใช้ prefix sum + hashmap เก็บ index ล่าสุดของแต่ละ sum
   • prefix[i] = min length จบ ≤ i
2. Suffix pass (ขวา→ซ้าย): หา min length subarray sum=k เริ่มที่หรือหลัง i
   • suffix[i] = min length เริ่ม ≥ i
3. Combine: min(prefix[i] + suffix[i+1]) สำหรับทุก i

โค้ด Python

class Solution:
    def solve(self, A, target):
        INF = float('inf')
        N = len(A)
        
        # Prefix: min length subarray sum=target ending at or before i
        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
        
        # Running minimum
        for i in range(1, N):
            prefix[i] = min(prefix[i], prefix[i-1])
        
        # Suffix: min length subarray sum=target starting at or after i
        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])
        
        # Combine
        ans = min(prefix[i] + suffix[i+1] for i in range(N-1))
        return ans if ans < INF else -1

# ทดสอบ
ob = Solution()
print(ob.solve([7, 10, -2, -1, 4, 3], 7))  # 3
print(ob.solve([1, 2, 3, 4, 5], 15))       # -1 (ไม่มี 2 ชุด)

ความซับซ้อน

• Time: O(n) - 3 passes
• Space: O(n) - prefix, suffix, hashmaps

ข้อสังเกต

• Subarray ต้องไม่ทับซ้อน → ใช้ prefix/suffix แยกฝั่ง
• Hashmap เก็บ prefix sum ล่าสุด/เก่าสุด เพื่อหา subarray sum=k
• Running min ทำให้ได้ min length จนถึงจุดนั้น