参考: @CyC2018

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

题目如下：

167.有序数组的 Two Sum（Easy）
633.两数平方和（Easy）
680.回文字符串（Easy）
88.归并两个有序数组（Easy）
141.判断链表是否存在环（Easy）
524.最长子序列（Medium）
345.反转字符串中的元音字符（Easy）

具体题目实现：

167.有序数组的 Two Sum（Easy）

题目描述：
在有序数组中找出两个数，使它们的和为 target。（不可以重复使用相同的元素）

输入：numbers = [2, 7, 11, 15], target = 9
输出：[1,2]

思路：
使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

• 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变大一些。

数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。

    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null) return null;
        int i = 0, j = numbers.length - 1;
        while (i < j) {    //i和j不能相同，否则就使用了相同元素
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                return new int[]{i + 1, j + 1};
            }else if (sum < target) {
                i++;
            }else {
                j--;
            }
        }
        return null; 
    }

633.两数平方和（Easy）

题目描述：
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 。

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

思路：

• 寻找范围：在元素为 0~target 的有序数组中查找两个数
• 本题和 167类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target
• 本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。怎样初始化右指针？设右指针为x，左指针固定为0，为了使的值尽可能接近target，我们可以将x取为sqrt(target)。也可以理解为x再怎样取也不会超过sqrt(target)。
• 因为最多只需要遍历一次0~sqrt(target)，所以时间复杂度为O(sqrt(target))。只使用了两个额外的变量，空间复杂度为O(1)。

    public boolean judgeSquareSum(int target) {
        if (target < 0) return false;
        int i = 0,j = (int) Math.sqrt(target);
        while (i <= j) {
            int sum = i * i + j * j;
            if (sum == target) {
                return true;
            } else if (sum > target) {
                j--;
            }else {
                i++;    //无论是i++还是i--都不影响空间大小的分配，所以空间复杂度为O(1)
            }
        }
        return false;
    }

680.回文字符串（Easy）

题目描述：
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
（“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。）

输入: "abca"
输出: True
解释: 你可以删除c字符。

思路：

保留题目

345.反转字符串中的元音字符（Easy）

题目描述：

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

输入："leetcode"
输出："leotcede"

思路：
使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。

为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。

• 时间复杂度为 O(N)：只需要遍历所有元素一次

• 空间复杂度 O(1)：只需要使用两个额外变量

  
  

private final static HashSet<Character> vowels = new HashSet<>(
        Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

public String reverseVowels(String s) {
    if (s == null) return null;
    int i = 0, j = s.length() - 1;
    char[] result = new char[s.length()];
    while (i <= j) {
        char ci = s.charAt(i);
        char cj = s.charAt(j);
        if (!vowels.contains(ci)) {
            result[i++] = ci;
        } else if (!vowels.contains(cj)) {
            result[j--] = cj;
        } else {
            result[i++] = cj;
            result[j--] = ci;
        }
    }
    return new String(result);
}