LeetCode #238 Product of Array Except Self: คูณซ้ายขวาโดยไม่ใช้หาร

โจทย์ให้ nums ความยาว n แล้วคืนอาร์เรย์ answer ที่ answer[i] เท่ากับผลคูณทุกตัวยกเว้น nums[i] ข้อจำกัดสำคัญคือ ห้ามใช้การหาร และ ideally เวลา O(n)

วิธีที่ 1: คูณทั้งหมดแล้วหาร (ไม่ผ่านโจทย์มาตรฐาน)

หาผลคูณรวม แล้วแต่ละช่องเป็น total / nums[i] พังเมื่อมีศูนย์ และผิดกติกาที่ห้ามหาร เก็บไว้เป็น anti-pattern

วิธีที่ 2: prefix และ suffix อาร์เรย์

prefix[i] = คูณทุกตัวก่อน i, suffix[i] = คูณทุกตัวหลัง i แล้ว answer[i] = prefix[i] * suffix[i] เวลา O(n) พื้นที่ O(n) นอกจากผลลัพธ์

วิธีที่ 3: เขียนลงคำตอบสองผ่าน (แนะนำหลัก)

ผ่านซ้ายไปขวาสะสมคูณซ้ายลง answer แล้วผ่านขวาไปซ้ายคูณด้วยคูณขวาที่สะสมในตัวแปรเดียว เวลา O(n) พื้นที่เสริม O(1) ตามนิยามโจทย์ที่ผลลัพธ์ไม่นับ

import unittest


def product_except_self(nums):
    n = len(nums)
    answer = [1] * n
    left = 1
    for i in range(n):
        answer[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer


def product_except_self_prefix_suffix(nums):
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    for i in range(1, n):
        prefix[i] = prefix[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] * nums[i + 1]
    return [prefix[i] * suffix[i] for i in range(n)]


class ProductExceptSelfTests(unittest.TestCase):
    def test_examples(self):
        cases = [
            ([1, 2, 3, 4], [24, 12, 8, 6]),
            ([-1, 1, 0, -3, 3], [0, 0, 9, 0, 0]),
            ([2, 3], [3, 2]),
        ]
        for nums, expected in cases:
            with self.subTest(nums=nums):
                self.assertEqual(product_except_self(nums), expected)
                self.assertEqual(product_except_self_prefix_suffix(nums), expected)

    def test_two_zeros(self):
        self.assertEqual(product_except_self([0, 0, 2]), [0, 0, 0])


if __name__ == "__main__":
    unittest.main()

เลือกตามสถานการณ์

สถานการณ์	วิธี
สอนแนวคิดแยกซ้าย/ขวา	prefix + suffix อาร์เรย์
ข้อสอบที่จำกัดพื้นที่เสริม	สองผ่านบนคำตอบ
มีสิทธิ์หารและไม่มีศูนย์	ยังไม่ใช้ — ผิดสเปกมาตรฐาน
สตรีมครั้งเดียวโดยไม่เก็บอาร์เรย์	โจทย์นี้ไม่รองรับโดยตรง

Recap

• แยกผลคูณซ้ายและขวาของแต่ละดัชนี
• ระวังศูนย์หนึ่งตัวกับหลายตัว
• อย่าใช้หารแม้ดูสั้นกว่า
• เทียบสองอิมพลีเมนต์บนเคสที่มีศูนย์ก่อนส่ง