นับสมาชิก x ที่มี x+1 อยู่ในลิสต์ Python

ภาพรวม

โจทย์นับจำนวนสมาชิก x ในลิสต์ที่มี x+1 อยู่ในลิสต์ด้วย (นับทุกครั้งที่เจอ x แม้จะซ้ำ)

ตัวอย่าง

อินพุต: [2, 3, 3, 4, 8]

• 2 → มี 3 อยู่ → นับ 1
• 3 (ตัวแรก) → มี 4 อยู่ → นับ 1
• 3 (ตัวที่สอง) → มี 4 อยู่ → นับ 1
• 4 → ไม่มี 5 → ไม่นับ
• 8 → ไม่มี 9 → ไม่นับ

รวม 3

โค้ด Python

class Solution:
    def solve(self, nums):
        s = set(nums)           # O(n) lookup
        count = 0
        for i in nums:
            if i + 1 in s:
                count += 1
        return count

ob = Solution()
nums = [2, 3, 3, 4, 8]
print(ob.solve(nums))

จุดสำคัญ

• ใช้ Set เพื่อ O(1) lookup แทน O(n) ของ list
• นับทุกครั้งที่เจอ x (รวม duplicate) ไม่นับ unique x
• เวลา O(n), พื้นที่ O(n)

ผลลัพธ์

3