同向双指针实战

互动

相向双指针：一头一尾

同向双指针：一前一后

两数之差

O(n)

很多数据量大的问题不允许用 hash 表。

当不能使用哈希表时：

• 可以在排序数据集上用数组 + 二分替代
• 或者题目要求不使用额外空间

public int[] twoSum(int[] nums, int target) {
    target = Math.abs(target);
    int j = 1;
    for (int i = 0; i < nums.length; i++) {
        j = Math.max(j, i + 1);
        while (j < nums.length && nums[j] - nums[i] < target) {
            j++;
        }
        if (j >= nums.length) {
            break;
        }
        if (nums[j] - nums[i] == target) {
            return new int[]{nums[i], nums[j]};
        }
    }

    return new int[]{-1, -1};
}

数组和字符串上的同向双指针总结

子数组或子字符串基本就是同向双指针

快慢指针

O(n) 空间的话，可以用 hash 表去记录是否有节点被走两次。