对撞型指针的本质是，不需要扫描多余的状态。在两边指针的判断之后，可以直接跳过其中一个指针与所有另外一面 index 组成的 pair.

2Sum/3Sum/4Sum实际上都是对冲型指针，但是比较有特点所以就特别放一个章节了。

Triangle Count

lint的一道题，总的思路对了，但是一开始受259影响，掉到了坑里，就是用 i = 1 to n 做最外循环，j 和 k 都在 i 后面。

• 这种思路的问题是，想 num[i] + num[j] > num[k]的话，如果当前条件不满足，j++ 和 k-- 都可以是对的。就违反了双指针不同程度上利用的单调性，一次只把一个指针往一个方向推，而且不回头。

• 所以顺着这个问题想，如果我们最外围遍历的是 k，而 i, j 都处于 k 的左面，那么每次就只有一个正确方向，挪动一个指针可以保证正确性了，即让 num[i] + num[j] 变大，或者变小。

public class Solution {
    public int triangleCount(int s[]) {
        if (s == null || s.length == 0) return 0;

        int count = 0;
        Arrays.sort(s);

        for (int i = 2; i < s.length; ++i) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (s[left] + s[right] <= s[i]) {
                    left++;
                } else {
                    count += (right - left);
                    right--;
                }
            }
        }
        return count;
    }
}

11. Container With Most Water / Container with most water

这种“灌水”类问题和双指针脱不开关系，都要根据木桶原理维护边界；在矩阵中是外围的一圈高度，在数组中就是左右两边的高度。

因为最低木板的高度决定水位，高位的木板有着另一种单调性，即高位木板向里移动的所有位置，形成的 container 水量都小于原来位置。

不过我觉得这题每次都拿俩木板出来一拼，这种问法有点傻。

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

        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            int width = right - left;
            int curArea = Math.min(height[left], height[right]) * width;
            max = Math.max(max, curArea);

            if (height[left] < height[right]) {
                left++;
            } else right--;
        }
        return max;
    }
}

42. Trapping Rain Water

这道题在前面单调栈里面已经见过了，也可以用双指针做，当然我还是更喜欢单调栈的做法。

木桶原理的算法版，最两边的板子形成一个木桶，由两块板子最低的那块决定水位。每次都从两边最低的方向向里扫描。

因为 i,j 当前高度未必是当前左右两边最高高度，每次更新的时候要注意维护下。

public class Solution {
    public int trap(int[] height) {
        if(height == null || height.length <= 2) return 0;
        int trapped = 0;
        int i = 0;
        int j = height.length - 1;

        int leftMax = height[i];
        int rightMax = height[j];

        while (i < j) {
            if (leftMax < rightMax) {
                if (i + 1 < height.length && height[i + 1] < leftMax) {
                    trapped += leftMax - height[i + 1];
                }
                i++;
                leftMax = Math.max(leftMax, height[i]);
            } else {
                if (j - 1 >= 0 && height[j - 1] < rightMax) {
                    trapped += rightMax - height[j - 1];
                }
                j--;
                rightMax = Math.max(rightMax, height[j]);
            }
        }
        return trapped;
    }
}

125. Valid Palindrome

Trivial problem 稍微烦一点的地方在于我们要忽略字符，并且不区分大小写（原始 String 里有字符也有大小写）

涉及到两个函数。

• Character.isLetterOrDigit(char chr)

• str.toLowerCase();

另外要注意的就是之前提到的双while循环，外层的判断条件也放到内层，否则容易越界。

public class Solution {
    public boolean isPalindrome(String s) {
        if (s.length() <= 1) return true;
        s = s.toLowerCase();

        int start = 0;
        int end = s.length() - 1;

        while (start < end) {
            while (start < end && !Character.isLetterOrDigit(s.charAt(start)))
                start++;
            while (start < end && !Character.isLetterOrDigit(s.charAt(end)))
                end--;
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else return false;
        }
        return true;
    }
}

345. Reverse Vowels of a String

public class Solution {
    public String reverseVowels(String s) {
        if (s == null || s.length() == 0) return s;
        String vowels = "aeiouAEIOU";
        char[] array = s.toCharArray();
        int i = 0;
        int j = array.length - 1;

        while (i < j) {
            while (i < j && !vowels.contains(array[i] + "")) i++;
            while (i < j && !vowels.contains(array[j] + "")) j--;
            char tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            i++;
            j--;
        }
        return new String(array);
    }
}

277. Find the Celebrity

暴力解是平方的时间复杂度，FB和Linkedin的面试题，考察一个双向思考从而降低时间复杂度的能力。

其实和双指针思想没有太大关系，只是用到了。不过能想到去用是很重要的。

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int i = 0;
        int j = n - 1;
        while (i < j) {
            if (knows(i, j)) i++;
            else j--;
        }
        for (int k = 0; k < n; ++k) {
            if (k == i) continue;
            if (!knows(k, i)) return -1;
            if (knows(i, k)) return -1;
        }
        return i;
    }
}