448_双指针面试题¶

def two_sum_sorted(numbers, target):
    """
    对撞指针：左指针指最小值，右指针指最大值
    和小了→左指针右移，和大了→右指针左移
    """
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]   # 题目要求1-indexed
        elif current_sum < target:
            left += 1                      # 和太小，左指针右移增大和
        else:
            right -= 1                     # 和太大，右指针左移减小和

    return [-1, -1]                        # 无解（题目保证有解）

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

def three_sum(nums):
    """
    思路：排序 + 固定一个数 + 对剩余用对撞双指针
    关键：跳过重复元素避免重复三元组
    """
    nums.sort()                            # 先排序，O(n log n)
    result = []

    for i in range(len(nums) - 2):
        if nums[i] > 0:                    # 最小的数都>0，不可能凑成0
            break

        if i > 0 and nums[i] == nums[i - 1]:  # 跳过重复的第一个数
            continue

        left, right = i + 1, len(nums) - 1  # 对剩余部分用对撞指针

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 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 total < 0:
                left += 1                  # 和太小，左指针右移
            else:
                right -= 1                 # 和太大，右指针左移

    return result

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

def remove_element(nums, val):
    """
    快慢指针：slow 指向下一个可写入位置，fast 扫描所有元素
    不等于val的元素写到slow位置
    """
    slow = 0                               # 慢指针：结果数组的末尾

    for fast in range(len(nums)):          # 快指针：遍历所有元素
        if nums[fast] != val:              # 不是要删除的值
            nums[slow] = nums[fast]        # 复制到slow位置
            slow += 1                      # slow前进

    return slow                            # slow就是新数组的长度

# 测试
nums = [3, 2, 2, 3]
k = remove_element(nums, 3)
print(k, nums[:k])  # 2 [2, 2]

nums = [0, 1, 2, 2, 3, 0, 4, 2]
k = remove_element(nums, 2)
print(k, nums[:k])  # 5 [0, 1, 3, 0, 4]

def trap(height):
    """
    对撞指针 + 动态维护左右最大高度

    核心思路：每个位置能接的雨水 = min(左边最高, 右边最高) - 当前高度
    用左右双指针，谁矮谁先处理（矮的那侧的max已经确定）
    """
    left, right = 0, len(height) - 1
    left_max = right_max = 0              # 左/右已知最大高度
    water = 0

    while left < right:
        if height[left] < height[right]:
            # 左边更矮，处理左边（左边max已确定，右边至少有right高的墙）
            if height[left] >= left_max:
                left_max = height[left]   # 更新左边最大值
            else:
                water += left_max - height[left]  # 能积水
            left += 1
        else:
            # 右边更矮，处理右边
            if height[right] >= right_max:
                right_max = height[right] # 更新右边最大值
            else:
                water += right_max - height[right]  # 能积水
            right -= 1

    return water

# 测试
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6
print(trap([4,2,0,3,2,5]))              # 9

# 对撞指针模板
left, right = 0, len(arr) - 1
while left < right:
    if condition(arr[left], arr[right]):
        # 找到满足条件的
        result.append(...)
        left += 1; right -= 1
    elif too_small:
        left += 1
    else:
        right -= 1

# 快慢指针模板（原地操作）
slow = 0
for fast in range(len(nums)):
    if keep(nums[fast]):               # 满足保留条件
        nums[slow] = nums[fast]
        slow += 1

# 判断回文
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1; right -= 1
    return True