双指针法在数组操作中的应用

# 1. 双指针法介绍

双指针法是一种常见的解决问题的技巧，在数组操作和链表操作中经常被使用。通过合理地设置两个指针，在遍历数组或链表时可以起到加速、优化算法的作用。在本章节中，我们将介绍双指针法的概念、原理，并与单指针法进行对比，同时对双指针法的时间复杂度进行分析。接下来我们将分别详细说明这三个方面的内容。

# 2. 双指针法的基本操作

双指针法是一种常见的数组操作技巧，通过使用多个指针在数组中进行遍历或操作，可以高效地解决各种问题。下面将介绍双指针法的基本操作及其应用场景。

### 2.1 快慢指针：解决查找问题

快慢指针常用于解决查找类问题，其中快指针每次走两步，慢指针每次走一步，通过它们之间的关系实现对数组的查找。

def findTarget(nums, target):
    slow, fast = 0, 0
    while fast < len(nums):
        # 操作逻辑
        if nums[fast] == target:
            return True
        fast += 1
    return False

**代码说明：**
- `slow`、`fast` 分别指向数组中的元素，通过移动 `slow` 和 `fast` 指针来实现对目标元素的查找。
- 当 `nums[fast]` 等于目标值 `target` 时，返回 `True` 表示找到目标。
- 如果遍历结束仍未找到目标，则返回 `False`。

### 2.2 左右指针：解决区间问题

左右指针常用于解决区间类问题，通过维护两个指针在数组两端，从而确定数组的区间范围。

public List<List<Integer>> findSubarrays(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    int left = 0, right = 0;
    while (right < nums.length) {
        // 操作逻辑
        if (满足条件) {
            results.add(Arrays.asList(left, right));
            left++;
        } else {
            right++;
        }
    }
    return results;
}

**代码说明：**
- `left`、`right` 分别指向数组的左右端点，通过移动两个指针来确定区间范围。
- 当满足特定条件时，将当前区间添加到结果集中，并将 `left` 指针向右移动；否则，将 `right` 指针向右移动继续寻找。

### 2.3 双向指针：解决两端夹逼问题

双向指针主要用于解决两端夹逼类问题，通过在数组两侧设置两个指针，逐步向中间夹逼以达到特定目的。

func twoSum(nums []int, target int) []int {
    left, right := 0, len(nums)-1
    for left < right {
        // 操作逻辑
        sum := nums[left] + nums[right]
        if sum == target {
            return []int{left, right}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return []int{-1, -1}
}

**代码说明：**
- `left`、`right` 分别指向数组两侧，通过移动两个指针逐步向中间夹逼，寻找满足条件的解。
- 当找到满足条件的解时，返回该解的索引；否则，根据情况移动 `left` 或 `right` 指针。

双指针法的基本操作包括快慢指针、左右指针和双向指针，在实际应用中可以根据具体问题灵活运用，提高算法效率。

# 3. 双指针法在数组查找中的应用

双指针法在数组操作中有着广泛的应用，特别是在查找和比较问题上能够提供高效的解决方案。下面将介绍双指针法在数组查找中的具体应用场景和操作方法。

#### 3.1 使用双指针法在有序数组中查找目标值

在有序数组中查找目标值是一个常见的问题，双指针法可以帮助我们在O(n)的时间复杂度内找到目标值的位置。具体操作步骤如下：

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] + nums[right] == target:
            return [left, right]
        elif nums[left] + nums[right] < target:
            left += 1
        else:
            right -= 1
    return []
# 测试
nums = [-2, 1, 2, 4, 7, 11]
target = 13
result = two_sum_sorted(nums, target)
print(result) # 输出：[2, 4]

**代码解释**：
- 使用两个指针`left`和`right`分别指向数组的起始位置和末尾位置。
- 每次比较`nums[left] + nums[right]`与目标值`target`的大小，逐步逼近目标值。

#### 3.2 利用双指针法在无序数组中查找两数之和

在无序数组中查找两数之和是LeetCode上的一道经典题目（LeetCode 1. Two Sum）。双指针法同样可以高效解决这个问题，代码如下：

def two_sum_unsorted(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return []
# 测试
nums = [2, 7, 11, 15]
target = 9
result = two_sum_unsorted(nums, target)
print(result) # 输出：[0,