Python - หาสับลิสต์ติดกันที่มีค่าติดกันและไม่ซ้ำกันยาวที่สุด

โจทย์: กำหนดรายการตัวเลข nums ที่ค่าทั้งหมดไม่ซ้ำกัน (Unique) หาความยาวของสับลิสต์ (Contiguous Sublist) ที่ยาวที่สุดซึ่งมีค่าที่ ติดกัน (Consecutive) หมายถึง ค่าสูงสุด - ค่าต่ำสุด = ความยาว - 1

ตัวอย่าง

Input: nums = [3, 6, 7, 5, 4, 9]
Output: 5
เหตุผล: สับลิสต์ [3, 6, 7, 5, 4] มีค่าตั้งแต่ 3 ถึง 7 (3,4,5,6,7) ติดกันครบ 5 ค่า

อัลกอริทึม: Brute Force O(n²) ด้วยการติดตาม Min/Max

เนื่องจากค่าทั้งหมด Unique แล้ว สับลิสต์จะมีค่าติดกันได้ก็ต่อเมื่อ max - min == j - i

ขั้นตอนการทำงาน

1. วนลูปจุดเริ่มต้น i ทุกตำแหน่ง
2. ติดตาม lhs (ค่าต่ำสุด) และ rhs (ค่าสูงสุด) ในสับลิสต์ nums[i:j+1]
3. หาก rhs - lhs == j - i แสดงว่าค่าติดกันครบ → อัปเดตคำตอบ

โค้ด Python

def solve(nums):
    ret = 0
    n = len(nums)
    
    for i in range(n):
        lhs = nums[i]
        rhs = nums[i]
        for j in range(i, n):
            lhs = min(lhs, nums[j])
            rhs = max(rhs, nums[j])
            if rhs - lhs == j - i:
                ret = max(ret, j - i + 1)
    
    return ret

# ทดสอบ
nums = [3, 6, 7, 5, 4, 9]
print(solve(nums))  # Output: 5

หมายเหตุสำคัญเกี่ยวกับตัวอย่าง Output

ในโจทย์ต้นฉบับ Output แสดงเป็น 1 ซึ่งดูเหมือนจะเป็นข้อผิดพลาด เพราะจากตัวอย่าง [3, 6, 7, 5, 4, 9] คำตอบที่ถูกต้องคือ 5 (สับลิสต์ [3,6,7,5,4] มีค่า 3,4,5,6,7 ติดกันครบ)

ความซับซ้อน

• Time Complexity: O(n²) - ลูปซ้อน 2 ชั้น
• Space Complexity: O(1) - ตัวแปรคงที่

การปรับปรุงเป็น O(n) (Advanced)

สามารถใช้ Sliding Window + Hash Set ได้ แต่ซับซ้อนกว่า เพราะต้องจัดการกับการขยาย/ย่อหน้าต่างพร้อมเช็ค Consecutive property

def solve_optimized(nums):
    """O(n) ใช้ Sliding Window + Set"""
    n = len(nums)
    left = 0
    seen = set()
    max_len = 0
    min_val = max_val = nums[0]
    
    for right in range(n):
        while nums[right] in seen:
            seen.remove(nums[left])
            left += 1
        seen.add(nums[right])
        min_val = min(min_val, nums[right])
        max_val = max(max_val, nums[right])
        
        # ตรวจสอบ consecutive property
        while max_val - min_val != right - left:
            seen.remove(nums[left])
            left += 1
            min_val = min(seen)
            max_val = max(seen)
        
        max_len = max(max_len, right - left + 1)
    
    return max_len

การทดสอบเพิ่มเติม

print(solve([1, 2, 3, 4]))        # 4
print(solve([10, 12, 11]))        # 3
print(solve([1, 3, 5, 7]))        # 1 (ไม่มีค่าติดกัน)
print(solve([5, 4, 3, 2, 1]))     # 5
print(solve([1, 5, 3, 4, 2]))     # 5 (ทั้งอาร์เรย์ 1-5)