双指针1：塔子哥的下标

前言

双指针算法概述

双指针算法（双指针技术）是一种在处理线性数据结构（如数组、链表）时常用的算法策略。它通过同时使用两个指针，以不同的方式遍历数据结构，从而优化时间复杂度或简化问题的解决过程。双指针算法广泛应用于各种经典问题，如数组排序、链表操作、字符串处理等。

双指针的常见类型

1. 快慢指针（快指针与慢指针）

   • 用途：常用于检测链表中的环、找到链表的中间节点等。
   • 原理：设定两个指针，快指针一次移动两步，慢指针一次移动一步。如果链表中存在环，快指针最终会与慢指针相遇；如果不存在环，快指针会先到达链表末尾。

2. 左右指针（双端指针）

   • 用途：常用于处理有序数组中的问题，如两数之和、三数之和、四数之和等。
   • 原理：设定一个指针指向数组的起始位置，另一个指针指向数组的末尾，根据当前指针对应的值与目标值的关系来移动指针，以缩小搜索范围。

3. 滑动窗口

   • 用途：用于解决字符串或数组中满足特定条件的子串或子数组问题，如最长不重复子串、最小覆盖子串等。
   • 原理：通过两个指针定义一个窗口的左右边界，根据窗口内元素是否满足条件来动态调整窗口的大小和位置。

题解

题面描述

给定一个排序数组 nums 和一个目标值 target，请你使用双指针的方法，找到数组中和为目标值的两个数，并返回它们的下标。保证只有一个解。

如果没有符合条件的两个数，返回 -1。

思路

分类

这道题属于 左右指针（双端指针） 的双指针算法类型。

解决思路

1. 初始化指针：

   • 设置左指针 left 指向数组的起始位置（索引为 0）。
   • 设置右指针 right 指向数组的末尾位置（索引为 n-1）。

   left = 0
   right = len(nums) - 1
   

2. 迭代查找：

   • 计算当前左指针和右指针所指元素的和 sum_val = nums[left] + nums[right]。

   • 比较 sum_val 与 target：

     • 如果 sum_val 等于 target，则找到目标对，返回它们的下标（注意转换为从 1 开始的索引）。

     if sum_val == target:
         return left + 1, right + 1  # 返回1-based索引
     

   • 如果 sum_val 小于 target，说明需要更大的数来增加和，因此将左指针 left 向右移动一位，以选择更大的数。

     elif sum_val < target:
         left += 1
     

   • 如果 sum_val 大于 target，说明需要更小的数来减少和，因此将右指针 right 向左移动一位，以选择更小的数。

     else:
         right -= 1
     

3. 终止条件：

   • 当左指针 left 不再小于右指针 right 时，停止迭代。如果此时仍未找到满足条件的两个数，返回 -1。

因为数组是排序数组，左指针右移时和一定是增大的，右指针左移时和一定是减小的，这样的移动可以保证不漏掉任何可能的解。

Python 实现代码

def find_two_sum(nums, target):
    left = 0
    right = len(nums) - 1
    
    while left < right:
        # 计算当前左指针和右指针所指元素的和
        sum_val = nums[left] + nums[right]
        
        if sum_val == target:
            # 找到符合条件的下标，注意转换为从1开始的下标
            return left + 1, right + 1  # 返回1-based索引
        elif sum_val < target:
            # 当前和小于目标值，左指针右移
            left += 1
        else:
            # 当前和大于目标值，右指针左移
            right -= 1
    
    # 如果没有找到符合条件的两个数
    return -1

# 读取输入
n = int(input())  # 数组的长度
nums = list(map(int, input().split()))  # 排序数组
target = int(input())  # 目标值

# 调用函数
result = find_two_sum(nums, target)

# 输出结果
if result == -1:
    print(-1)
else:
    print(result[0], result[1])

题目描述：

给定一个排序数组 $\text{nums}$ 和一个目标值 $\text{target}$，请你使用双指针的方法，找到数组中和为目标值的两个数，并返回它们的下标。保证只有一个解。

如果没有符合条件的两个数，返回 $-1$。

注意：

• 数组中的下标是从 $1$ 开始的，而不是从 $0$ 开始。
• 如果存在多个解，返回第一个满足条件的下标。

输入

• 一个整数$n$,$（1 ≤ n ≤ 10^5）$：表示数组的大小。
• 一个长度为$n$的排序数组$\text{nums}$,$（1 ≤ \text{nums}[i] ≤ 10^9$，数组已按升序排列）。
• 一个整数$\text{target}$,$（1 ≤ \text{target} ≤ 2 \times 10^9)$，表示目标值。

输出

• 如果找到两个数的和为目标值，返回这两个数的下标
• 如果没有满足条件的两个数，返回 -1。

示例

示例 1:

输入：

4
2 7 11 15
9

输出：

1 2

解释：数组中的 2 和 7 的和等于目标值 9，它们的下标分别为 1 和 2。

示例 2:

输入：

3
1 2 3
6

输出：

-1

解释：数组中的数字没有两个数的和为目标值 6。