双指针（Two Pointers）

双指针（Two Pointers）

✅ 算法介绍

双指针是一种使用两个指针变量（通常表示位置或索引）在数据结构上进行遍历和处理的技巧。两个指针可以是：

• 同向移动（常用于遍历子数组、滑动窗口）
• 反向逼近（常用于排序数组中找特定组合，如两数之和）

通过合理控制两个指针的移动，可以减少不必要的遍历，提高效率。

---

🧭 适用场景

• 有序数组中的配对问题（如两数之和、三数之和）
• 子串、子数组求解（最长无重复子串、最大子数组长度）
• 链表操作（如判断是否为回文）
• 去重、合并两个有序数组等操作

---

⏱️ 时间复杂度 & 空间复杂度

类别	复杂度
时间复杂度	O(n)
空间复杂度	O(1)（仅用两个变量）

---

🐍 Python 示例：有序数组中找两数之和为 target

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1
    return []

---

☕ Java 实现

public int[] twoSumSorted(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

---

🐹 Go 实现

func twoSumSorted(arr []int, target int) []int {
    left, right := 0, len(arr)-1
    for left < right {
        sum := arr[left] + arr[right]
        if sum == target {
            return []int{left, right}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return []int{}
}

---

🌐 JavaScript 实现

function twoSumSorted(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        else if (sum < target) left++;
        else right--;
    }
    return [];
}

---

🧵 C 实现

int* twoSumSorted(int* arr, int size, int target, int* returnSize) {
    int* result = malloc(sizeof(int) * 2);
    int left = 0, right = size - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            result[0] = left;
            result[1] = right;
            *returnSize = 2;
            return result;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    *returnSize = 0;
    return NULL;
}

---

🧠 C++ 实现

vector<int> twoSumSorted(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return {left, right};
        else if (sum < target) left++;
        else right--;
    }
    return {};
}

---

✨ 小提示

• 常见组合：while (left < right) 是经典结构
• 可用于排序 + 去重类场景，如三数之和、四数之和等
• 双指针也适用于链表（快慢指针）
• 和滑动窗口容易混淆：滑动窗口更多用于“区间满足某条件”，双指针更多是“两个变量协同推进”