Kỹ thuật hai con trỏ

def tim_cap_tong(arr, target):
    """
    Tìm cặp có tổng = target trong mảng đã sắp xếp.
    O(n) thay vì O(n²) của cách duyệt hai vòng.
    """
    left, right = 0, len(arr) - 1
    while left < right:
        tong = arr[left] + arr[right]
        if tong == target:
            return (arr[left], arr[right])
        elif tong < target:
            left += 1    # Tăng tổng bằng cách tăng left
        else:
            right -= 1   # Giảm tổng bằng cách giảm right
    return None

sorted_arr = [1, 2, 4, 6, 8, 9, 14, 15]
print(tim_cap_tong(sorted_arr, 14))   # (6, 8)
print(tim_cap_tong(sorted_arr, 5))    # None

def xoa_trung(arr):
    """
    Loại bỏ phần tử trùng trong mảng đã sắp xếp, tại chỗ.
    slow: vị trí tiếp theo cần ghi, fast: đi tìm phần tử chưa gặp.
    """
    if not arr:
        return 0

    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1   # Độ dài phần không trùng

arr = [1, 1, 2, 3, 3, 4, 5, 5]
k = xoa_trung(arr)
print(arr[:k])   # [1, 2, 3, 4, 5]

def la_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(la_palindrome("racecar"))   # True
print(la_palindrome("hello"))     # False
print(la_palindrome("abcba"))     # True
print(la_palindrome("a"))         # True

def nuoc_nhieu_nhat(heights):
    """
    Hai con trỏ từ hai đầu: luôn di chuyển con trỏ có chiều cao thấp hơn
    vì đó là yếu tố giới hạn diện tích.
    """
    left, right = 0, len(heights) - 1
    max_nuoc = 0
    while left < right:
        chieu_cao = min(heights[left], heights[right])
        chieu_rong = right - left
        max_nuoc = max(max_nuoc, chieu_cao * chieu_rong)
        if heights[left] <= heights[right]:
            left += 1
        else:
            right -= 1
    return max_nuoc

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

def ba_so_tong_bang_0(nums):
    """
    Sắp xếp dãy, duyệt từng phần tử làm 'a',
    rồi dùng two pointers cho b và c.
    """
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue   # Bỏ qua trùng lặp ở vị trí i
        left, right = i + 1, len(nums) - 1
        while left < right:
            tong = nums[i] + nums[left] + nums[right]
            if tong == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1   # Bỏ qua trùng lặp
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif tong < 0:
                left += 1
            else:
                right -= 1
    return result

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

print(ba_so_tong_bang_0([0, 0, 0]))
# [[0, 0, 0]]