双指针

验证回文串

• 双指针

public boolean isPalindrome(String s) {
    if (" ".equals(s)) return true; // 如果字符串为空，则返回true 
    int left = 0, right = s.length()-1;
    while(left <= right){
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { // 如果左指针指向的字符不是字母或数字，则移动左指针
            left++;
        }
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { // 如果右指针指向的字符不是字母或数字，则移动右指针
            right--;
        }
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { // 如果左右指针指向的字符不相同，则返回false
            return false;
        }
        left++; // 移动左指针
        right--; // 移动右指针
    }
    return true;
}

判断子序列

• 双指针
• 也可以使用动态规划

public boolean isSubsequence(String s, String t) { //s是子序列，t是母序列
    int n = s.length(), m = t.length(); // 获取s和t的长度
    int i = 0, j = 0; // 初始化s和t的指针
    while (i < n && j < m) { // 如果s的指针小于s的长度且t的指针小于t的长度，则继续遍历
        if (s.charAt(i) == t.charAt(j)) { // 如果当前元素是子序列的元素，则移动s的指针
            i++;
        }
        j++; // 移动t的指针，无论是否匹配到，t的指针都要移动
    }
    return i == n; // 如果s的指针等于s的长度，则说明s是t的子序列
  }

两数之和II 输入有序数组

• 双指针

public int[] twoSum(int[] numbers, int target) {
    int left = 0; // 左指针
    int right = numbers.length - 1; // 右指针
    while (left < right) {
        int sum = numbers[left] + numbers[right]; // 计算当前两个指针指向的元素的和
        if (sum == target) { // 如果和等于目标值，则返回两个指针的索引
            return new int[]{left + 1, right + 1}; // 返回两个指针的索引，注意返回的是索引+1，因为题目要求返回的是索引+1
        } else if (sum < target) {
            left++; // 如果和小于目标值，则移动左指针
        } else {
            right--; // 如果和大于目标值，则移动右指针
        }
    }
    return new int[]{-1, -1}; // 找不到两个数
}

盛水最多的容器

• 使用双指针，左指针指向数组开始，右指针指向数组尾部
• 区域受限于较短的边, 每次移动较短的边, 然后计算面积, 更新最大面积

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    while (left < right) { // 找出所有可能的面积
        int area = Math.min(height[left], height[right]) * (right - left); // 由两边较短的边决定水的高度 area=高*宽
        maxArea = Math.max(maxArea, area); // 更新最大面积
        if (height[left] < height[right]) { // 如果左边较短，则移动左边
            left++; 
        } else {
            right--; 
        }
    }
    return maxArea;
}