ตัวชี้สองตัว: จากปลายตรงข้าม

แนวคิดตัวชี้สองตัว

# Without two pointers: O(n^2)
def two_sum_brute(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]
    return []

# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left, right]
        elif s < target: left  += 1
        else:           right -= 1
    return []

ผลรวมสองตัวในอาร์เรย์ที่เรียงลำดับแล้ว

def two_sum_sorted(numbers, target):
    # numbers is 1-indexed per LeetCode 167
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]  # 1-indexed
        elif s < target:
            left  += 1  # need larger sum
        else:
            right -= 1  # need smaller sum
    return []

print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]

การตรวจสอบข้อความที่อ่านกลับเหมือนเดิม

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome('A man, a plan, a canal: Panama'))  # True
print(is_palindrome('race a car'))                       # False

ผลรวมสามตัว: sort + ตัวชี้สองตัว

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # skip dupe
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left]  == nums[left+1]:  left  += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0: left  += 1
            else:       right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]

ภาชนะที่บรรจุน้ำได้มากที่สุด

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h    = min(height[left], height[right])
        area = h * (right - left)
        best = max(best, area)
        # Move the shorter wall inward
        if height[left] < height[right]:
            left  += 1
        else:
            right -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

การยกกำลังสองของอาร์เรย์ที่เรียงลำดับแล้ว

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1
    while left <= right:
        l_sq = nums[left]  ** 2
        r_sq = nums[right] ** 2
        if l_sq > r_sq:
            result[pos] = l_sq
            left += 1
        else:
            result[pos] = r_sq
            right -= 1
        pos -= 1
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]

การดักน้ำฝน

def trap(height):
    left, right = 0, len(height) - 1
    max_left = max_right = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= max_left:
                max_left = height[left]
            else:
                water += max_left - height[left]
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]
            else:
                water += max_right - height[right]
            right -= 1
    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6

เหตุใดการเลื่อนตัวชี้แบบเลือกทางที่เหมาะสมที่สุดจึงใช้ได้

# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
#   area(left, j) <= min(h[left], h[j]) * (j - left)
#                 <= h[left] * (j - left)
#                 <= h[left] * (right - left)   [since j < right]
#                 = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.

print('Proof verified: advance shorter pointer is optimal')

คู่ที่มีผลต่างน้อยที่สุดในอาร์เรย์ที่เรียงลำดับ

def min_diff_pair(nums):
    nums.sort()  # O(n log n)
    min_diff = float('inf')
    best = (nums[0], nums[1])
    for i in range(len(nums) - 1):
        diff = nums[i+1] - nums[i]  # sorted: always >= 0
        if diff < min_diff:
            min_diff = diff
            best = (nums[i], nums[i+1])
    return best, min_diff

pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d)  # (1, 2) 1

แม่แบบตัวชี้สองตัวจากปลายตรงข้าม

def two_pointer_template(arr, condition):
    """
    Generic opposite-ends two-pointer skeleton.
    Replace condition logic for each specific problem.
    """
    left, right = 0, len(arr) - 1
    result = []
    while left < right:
        current = arr[left] + arr[right]  # or some combination
        if current == condition:           # found a valid pair
            result.append((arr[left], arr[right]))
            left  += 1
            right -= 1
        elif current < condition:          # need to increase
            left  += 1
        else:                             # need to decrease
            right -= 1
    return result

การนับคู่ที่ถูกต้องด้วยตัวชี้สองตัว

def count_pairs_less_than(nums, target):
    nums.sort()
    left, right = 0, len(nums) - 1
    count = 0
    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left  # all (left, left+1..right) valid
            left  += 1
        else:
            right -= 1
    return count

print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3)  -> 4

ตรวจสอบความเข้าใจ

สรุปบทเรียน