เทคนิคที่เจอบ่อย (Common Patterns)

# เช็คพาลินโดรมด้วยตัวชี้หัว-ท้าย
def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i, j = i + 1, j - 1   # ขยับเข้าหากัน
    return True

print(is_palindrome("level"))  # True

# หาคู่ที่บวกกันได้ target ในลิสต์ที่เรียงแล้ว
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)

# หาผลรวมมากสุดของ subarray ความยาว k
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  (5+1+3)

# Two Sum: หา index ของคู่ที่บวกได้ target
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]  (2 + 7)

# เช็คว่ามีค่าซ้ำไหม ด้วย set — O(n)
def has_dup(nums):
    return len(set(nums)) != len(nums)
print(has_dup([1, 2, 3, 2]))       # True