เทคนิคสัมภาษณ์ (Patterns)

# วิธีช้า O(n²): วนทุกคู่
def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# วิธีเร็ว O(n): ใช้ dict จำสิ่งที่เคยเห็น
def two_sum(nums, target):
    seen = {}                     # ค่า -> index
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:          # เคยเห็นตัวที่ต้องการแล้ว
            return [seen[need], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

def max_sum_k(arr, k):
    window = sum(arr[:k])         # ผลรวมหน้าต่างแรก
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # เพิ่มตัวใหม่ ลบตัวเก่า
        best = max(best, window)
    return best

print(max_sum_k([2, 1, 5, 1, 3, 2], 3))  # 9

def longest_unique(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:    # มีตัวซ้ำ หดหน้าต่างจากซ้าย
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))  # 3
print(longest_unique("bbbbb"))     # 1

def two_sum_sorted(arr, target):
    i, j = 0, len(arr) - 1
    while i < j:
        s = arr[i] + arr[j]
        if s == target:
            return (arr[i], arr[j])
        elif s < target:
            i += 1            # น้อยไป ขยับซ้ายขึ้น
        else:
            j -= 1            # มากไป ขยับขวาลง
    return None

print(two_sum_sorted([1, 3, 5, 7, 9], 12))  # (3, 9)