双指针

互动

相向双指针：一头一尾

同向双指针：一前一后

两数之差

On

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

当不能使用哈希表时

可以在排序数据集上进行二分来替代
不能使用哈希表的情况比如数据集很大
或者题目要求不适用额外空间

数组+二分可以起到hashmap的作用

一个for，一个while

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};
}

同向双指针模板

双指针：不产生额外空间

移除重复元素

int deduplication(int[] nums) {
	if (nums == null || nums.length == 0) {
        return 0;
	}
    
    Arrays.sort(nums);
    int i, j = 1;
    for (i = 0; i < nums.length; i++) {
        while (j < nums.length && nums[j] == nums[i]) {
            j++;
        }
        if (j >= nums.lenght) {
            break;
        }
        nums[i + 1] = nums[j];
    }
    
    return i + 1;
}

滑动窗口求和

windowSum

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

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

数组和字符串的问题有很多题都是和双指针，特别是同向双指针有关

通常问题让我们求是一段子数组或者子字符串

所以遇到“子数组 SubArray” 和“子字符串 SubString” 就需要往同向双指针思考

快慢指针

On空间的话，可以用hash表去记录是否有节点被走两次