Collide Pointers - Githubissues

双指针（two pointer）是 Leetcode 中重要的解题技巧，滑动窗口也是一种双指针技巧。窗口的滑动是 lo 和 hi 两个指针分别向右滑动。此外，两个指针如果分别从低位和高位相向滑动，那么就是对撞指针。

对撞指针的用法很多种，对于两边夹，单调性的数组（已排序的数组），以及 partition 区分都非常有用。下面就通过一些简单的题目来介绍对撞指针。

两边夹

对撞，顾名思义，就是相向而行，直到碰撞。leetcode的 125 验证回文串题要求是验证回文串。

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。
示例 1: 输入: "A man, a plan, a canal: Panama" 输出: true
示例 2: 输入: "race a car" 输出: false

所谓回文串就是从左到右扫描的字符，和从右到左扫描的字符一模一样。

回到题目本身，既然回文是为了验证从左往右和从右往左都必须一样。那么就可以设置两个指针，一个分别从左往右扫描，另外一个从右往左扫描。扫描的过程中，比对指针所对应的字符。

例如下图分别从左往右和从右往左：

实际上，因为回文本身是对称的，因此在比对的时候，不需要设置循环为 while(lo < s.length()，即完全地从左到右。而是从左到右和从右到左一起移动，一旦相撞，则停止。即循环条件为 while(lo < hi)。l <= r 的时候，表示两个指针重叠，此时字符相对自身也是属于回文，也可以这样写，只是这题没有必要。

在滑动窗口中，通常设置窗口的大小为 [lo, hi) 左闭右开的区间，为了方便计算窗口的大小 hi - lo，而在对撞指针中，两个指针的元素都需要使用，即都是闭合的，可以设置为 [l, r] 的区间内向中间靠拢。

class Solution {
    public boolean isPalindrome(String s) {

        if(s == null || s.length() <= 1) {
            return true;
        }

        int lo = 0, hi = s.length()-1;

        while(lo < hi) {
            while(lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) {
                lo++;
            }

            while(lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) {
                hi--;
            }

            if(Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi))) {
                return false;
            } else {
                lo++;
                hi--;
            }
        }

        return true;
    }
}

对于两边夹的对撞指针，核心就是在处理两边指针扫描元素的时候进行逻辑判断，以便移动指针。当前题目的指针是同步移动，类似的还有下面一题。

344. Reverse String

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2：输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

解题思路类似，初始化连个指针 l 和 r，分别指向数组的第一个元素和最后一个元素，然后同步向中间靠拢，靠拢的过程中交互两个指针的元素。

class Solution {
    public void reverseString(char[] s) {
        if(s == null || s.length <= 1) {
            return;
        }

        int lo = 0, hi = s.length-1;
        while(lo < hi) {
            char temp = s[lo];
            s[lo] = s[hi];
            s[hi] = temp;
            lo++;
            hi--;
        }
    }
}

从上面两题可以初步的感受对撞指针的套路。即左右指针相向移动，上面的两题是同步移动的。还有其他的题目，指针的移动未必是同步的，移动前提需要判断一些条件。当条件满足之后适当的移动左边或者右边，最终相撞求解返回。例如

11. Container With Most Water

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的> 两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。

由题意可知，盛水的容量来与数组两个数字之间有关，其中数字越小（高度越短）决定了最终的盛水量，类似木桶理论。每两个数字可以组成一个容器，一个数字则无法盛水。与滑动窗口类似，可以找出任意两个数字组成的一个窗口，求解其值存储。当所有窗口都计算完毕之后返回最大的值即可。

与滑动窗口又不一样的地方在于，窗口不是从左往右滑动。而是使用了对撞指针相向缩小。初始化的窗口为数组的最大宽度，然后左右指针相向移动。

什么时候移动呢？由 [l, r] 组成的窗口，其盛水量为 min(l, r) * (r - l)。由此可见，r-l 只能更小，想要这个表达式更大，只能找到更高的数。因此想要盛更多的水，只有把最矮的设法变高，即高度更矮的指针进行移动。如果移动更高的指针，那么 r - l 距离变小了，同时 min(l, r) 也不会更大，只会更小。最终代码如下：

class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length <= 1) {
            return 0;
        }

        int lo = 0, hi = height.length-1;
        int localArea = 0, maxArea = 0;

        while(lo < hi) {
            localArea = Math.min(height[lo], height[hi]) * (hi-lo);
            maxArea = Math.max(maxArea, localArea);
            if(height[lo] < height[hi]) {
                lo++;
            } else {
                hi--;
            }
        }

        return maxArea;
    }
}

从上面的例子可以看出，对撞指针的一般模板是设置 [l, r], 然后再 l < r 的条件中缩小窗口，直到指针相撞退出。左右指针向中间靠拢，最多移动单位不过为数组的长度，即时间复杂度为 O(n)。

与上面一题类似还有一道接雨水的问题。

42. Trapping Rain Water

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

这一题与上一题的要求不一样，每个数组的元素自身的高度对于盛水量有关系。上一题是两个元素之间的，元素本身没有关系。这一题恰好相反。当前元素所能盛水的大小，取决于其左边最高的元素和其右边最高元素中比较矮的那个，同时需要减掉自身的高度。如下图

因此假设有一个指针从左往右进行移动，那么它当前接水的容量来自它左边最高和它右边最高的数。如何求出左边和右边的最高数呢？

一个简单办法就是使用对撞指针，l 和 r 分别向中间靠拢，移动的过程中可以找出 [0, l] 中间的最高 l_max 和 [r, len]中间的最高 r_max，而当前的指针可以取 min(l_max, r_max) 中的部分。如下图

当 l , r 分别在上图的过程中，l 所能盛水的容量是 height[l_max] - height[l]，此时是0，然后 l 向右移动。此时 l 能盛水依然是 height[l_max] - height[l] 则是一个单位。依次类推，只要 l_max < r_max ，那么就移动 l 指针，直到 l 等于 r。如果 l_max 小于 r_max，也就是上图的对称过程，就不再赘述。具体可以看代码：

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length <= 1) {
            return 0;
        }

        int lo = 0, hi = height.length-1;
        int leftMax = height[lo], rightMax = height[hi];
        int res = 0;

        while(lo < hi) {
            leftMax = Math.max(leftMax, height[lo]);
            rightMax = Math.max(rightMax, height[hi]);

            if(leftMax < rightMax) {
                res += leftMax - height[lo++];
            } else {
                res += rightMax - height[hi--];
            }
        }

        return res;
    }
}

对排序好的数据进行对撞

对撞指针还有一个典型的应用场景就是针对已经排序的数组进行碰撞。

leetcode的 1. Two Sum 特别经典。使用哈希字典能很快解题。其中第167. Two Sum II - Input array is sorted 题，将输入的数组排定为有序数组。

有序的数组就比好办了，对于两个数之和，如何大于target，那么就需要减少两数之和，自然就是 r 指针向左移动，如果小于target元素，那么就需要增加两数之和，自然就是移动左边的r指针。

    public int[] twoSum(int[] numbers, int target) {
        int lo = 0, hi = numbers.length-1;
        while(lo < hi) {
            int sum = numbers[lo] + numbers[hi];
            if(sum == target) {
                return new int[]{lo+1, hi+1};
            } else if(sum < target) {
                lo++;
            } else {
                hi--;
            }
        }
        return new int[] {-1, -1};
    }
}

与两数之和类似的自然就是三数之和，三数之和的注意点就是需要先对数组进行排序，然后可以对数组进行迭代。迭代过程中，就以当前元素i 到末尾的数组为子数组 [i, len]，然后转变为两数之和进行处理，即寻找子数组的 pair 对。

15. 3Sum

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为： [[-1, 0, 1], [-1, -1, 2]]

由于题目不能有重复的数组，因此对于连续的两个相同的数字，其子数组是一样的，需要先去重。同时一旦找到了两个合法的数字，l 和 r尚不能停止，因为 [l, r] 之间可能有多个符合题意的pair对，同时在寻找剩余 pair对的时候也需要注意去重。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0; i < nums.length-2; i++) {
            if(i != 0 && nums[i-1] == nums[i]) {
                continue;
            }

            int lo = i+1, hi = nums.length-1;
            while(lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if(sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[lo++], nums[hi--]));
                    while(lo < hi && nums[lo] == nums[lo-1]) lo++;
                    while(lo < hi && nums[hi] == nums[hi+1]) hi--;
                } else if(sum < 0) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }

        return res;
    }
}

三数之和的变种有一题为 16. 3Sum Closest。初看会觉得比三数之和复杂，其实更简单。所谓最近，即 pair对的和与 target 的差的绝对值就是距离。初始化一个three sum，当距离更短的时候更新three sum，同时缩小对撞指针。题目如下

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

代码如下:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];

        for(int i = 0; i < nums.length-2; i++) {
            int lo = i+1, hi = nums.length-1;
            while(lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if(Math.abs(target-sum) < Math.abs(target-closestSum)) {
                    closestSum = sum;
                }
                if(sum == target) {
                    return sum;
                } else if(sum < target) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }

        return closestSum;
    }
}

移动指针的技巧很简单，两数之和与target的距离有大有小。如果这个值大于 0，那么可以减少两数之和，即r指针向左移动，反之则表示这个和可以增大，即 l 指针右移。正好等于0，由于题目保证了解唯一，那么就可以直接返回了。

此类两数，三数甚至四数之和，都是对撞指针对单调数组的一种处理方式。通过对数组的排序，可以明确的知道 l 和 r 指针的和或者差应该扩大还是缩小。

18. 4Sum

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。


class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);

    for(int i = 0; i < nums.length-3; i++) {
        if(i != 0 && nums[i] == nums[i-1]) continue;
        for(int j = i+1; j < nums.length-2; j++) {
            if(j > i+1 && nums[j] == nums[j-1]) continue;
            findTwoSumWithTarget(res, nums, i, j, target);
        }
    }

    return res;
}

private void findTwoSumWithTarget(List<List<Integer>> res, int[] nums, int i, int j, int target) {
    int left = j+1, right = nums.length-1;
    while(left < right) {
        int sum = nums[i] + nums[j] + nums[left] + nums[right];
        if(sum == target) {
            res.add(Arrays.asList(nums[i], nums[j], nums[left++], nums[right--]));
            while(left < right && nums[left] == nums[left-1]) left++;
            while(left < right && nums[right] == nums[right+1]) right--;
         } else if(sum < target) {
            left++;
        } else {
            right--;
        }
    }
}

}

Partition

对于已排序的数组可以使用对撞指针，而对撞指针本身也是处理排序的一种重要技巧。

快速排序的思想就是选取一个 partition 元素，分别将比其小和比其大的元素区分出来。其中使用对撞指针很容易实现类似的功能。

75. 颜色分类就是应用对撞指针求解 partition 问题。

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
Example 1: Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Example 2: Input: nums = [2,0,1] Output: [0,1,2]

这道题也称之为荷兰旗帜问题，即三个数字分别表示荷兰国旗🇳🇱三种颜色。之所以是荷兰，最早提出这个问题的就是大名鼎鼎的荷兰计算机科学家 Edsger Dijkstra 提出的.

GRAPH VISUALIZATION TO BE ADDED

class Solution {
    public void sortColors(int[] nums) {
        int lo = 0, hi = nums.length-1;
        int i = 0;

        // THIS IS NOT THE i <= nums.length!!!!!
        while(i <= hi) {
            if(nums[i] == 0) {
                swap(nums, i, lo);
                i++;
                lo++;
            } else if(nums[i] == 1) {
                i++;
            } else { // nums[i] == 2
                swap(nums, i, hi);
                hi--;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

滑动窗口

对撞指针和滑动窗口都是双指针的一种，回忆滑动窗口可以知道。往往滑动窗口的过程有多个解，最终问题是需要求最优解。如果需要枚举所有的解，那么使用滑动窗口需要特别注意，如滑动窗口的重复解。请看下面一题：

713. Subarray Product Less Than K

给定一个正整数数组 nums。找出该数组内乘积小于 k 的连续的子数组的个数。

从题意可知，特别像滑动窗口的问题。通常滑动窗口会问符合要求的最小连续子数组。如果使用滑动窗口过程中。如果直接使用滑动窗口，会发现遗漏一些解。如果针对每个元素都使用一次滑动窗口，复杂度暂且不说，重复的解也会出现。

针对这题，既要配合滑动窗口，也要合理的使用对撞指针。使用滑动窗口确定一个可能解，由于乘积最小，那么窗口最右边的元素必须包含，那么再求解这个窗口包含最有元素的子数组，就是窗口内的所有解。具体代码如下：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {

        int lo = 0, product = 1, res = 0;

        for(int hi = 0; hi < nums.length; hi++) {
            product *= nums[hi];
            while(product >= k && lo <= hi) {
                product /= nums[lo++];
            }

            res += hi - lo + 1;
        }

        return res;
    }
}

MISC.

581. Shortest Unsorted Continuous Subarray

给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。

一开始看见这题，我们可能会想到这样一个思路：

我们从左边开始遍历数组，找到第一个数字是无序的，即nums[i] > num[i+1]。相似的，从右边开始遍历数组，找到第一个数字是无序的nums[j] < nums[j-1]，然后我们把[i, j]这个区间的subarray重新sort一下，就可以保证我们整个array都是sorted的了。

但是这样做有什么样的问题呢？

我们来举个例子，这里有一个这样的数组：

[1, **3, 2, 0, -1**, 7, 10]

我们首先从左边开始遍历，发现第一个out of order的数字是2，即nums[1] < nums[2]
接着我们从右边开始遍历，发现第一个out of order的数字是0，即nums[3] < nums[4]

如果我们把3到-1之间的数字sort一下，我们会得到：

[1, **-1, 0, 2, 3**, 7, 10]

我们发现它还不是完全sort的，那为什么会发生这样的情况呢？

这里的问题就在于，现在最小的-1，告诉我们我们应该往左边移一些位置，直到把左边所有比-1大的数都包括进去才行。右边的3也会有同样的问题。

那我们的思路应该改进到这样：

From the beginning and end of the array, find the first elements that are out of the sorting order. The two elements will be our candidate subarray.
Find the maximum and minimum of this subarray.
Extend the subarray from beginning to include any number which is bigger than the minimum of the subarray.
Similarly, extend the subarray from the end to include any number which is smaller than the maximum of the subarray.

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int lo = 0, hi = nums.length-1;

        // find the first number out of sorting order from the beginning
        while(lo < nums.length-1 && nums[lo] <= nums[lo+1]) {
            lo++;
        }

        if(lo == nums.length-1) { // if the array is sorted
            return 0;
        }

        // find the first number out of sorting order from the end
        while(hi > 0 && nums[hi] >= nums[hi-1]) {
            hi--;
        }

        // find the maximum and minimum of the subarray
        int subarrayMin = Integer.MAX_VALUE, subarrayMax = Integer.MIN_VALUE;
        for(int i = lo; i <= hi; i++) {
            subarrayMin = Math.min(subarrayMin, nums[i]);
            subarrayMax = Math.max(subarrayMax, nums[i]);
        }

        // extend the subarray to include any number which is bigger than the minimum of the subarray 
        while(lo > 0 && nums[lo-1] > subarrayMin) {
            lo--;
        }

        // extend the subarray to include any number which is smaller than the maximum of the subarray
        while(hi < nums.length-1 && nums[hi+1] < subarrayMax) {
            hi++;
        }

        return hi-lo+1;
    }
}

844. Backspace String Compare

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。

这道题可以每个string的最后开始遍历，每次遍历时找到下一个含有字母的index，如果碰见了backspace，就跳过，直到找到合法的字符为止。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int index1 = s.length()-1, index2 = t.length()-1;

        while(index1 >= 0 || index2 >= 0) {
            int i1 = getNextValidIndex(s, index1);
            int i2 = getNextValidIndex(t, index2);

            if(i1 < 0 && i2 < 0) {
                return true;
            }

            if(i1 < 0 || i2 < 0) {
                return false;
            }

            if(s.charAt(i1) != t.charAt(i2)) {
                return false;
            }

            index1 = i1-1;
            index2 = i2-1;
        }

        return true;
    }

    private int getNextValidIndex(String s, int index) {
        int backspaceNum = 0;
        while(index >= 0) {
            if(s.charAt(index) == '#') {
                backspaceNum++;
            } else if(backspaceNum > 0) {
                backspaceNum--;
            } else {
                break;
            }
            index--;
        }
        return index;
    }
}

xiedaxia1hao / leetcode_pattern

Collide Pointers #18

两边夹

对排序好的数据进行对撞

Partition

滑动窗口

MISC.