双指针

验证回文串 - LeetCode 125

• 双指针

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

判断子序列 - LeetCode 392

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

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 输入有序数组 - LeetCode 167

• 双指针

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}; // 找不到两个数
}

盛水最多的容器 - LeetCode 11

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

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

字符串相加 - LeetCode 415

public String addStrings(String num1, String num2) {
    int i = num1.length()-1, j = num2.length()-1; // 从后往前遍历
    int add = 0; // 进位
    StringBuilder sb = new StringBuilder(); // 存储结果
    while(i>=0 || j>=0 || add!=0){ // 如果还有进位或者还有数字
        int x = i>=0 ? num1.charAt(i) - '0' : 0; // 如果还有数字，则取数字 如果已经遍历完，则取0
        int y = j>=0 ? num2.charAt(j) - '0' : 0; // 如果还有数字，则取数字 如果已经遍历完，则取0
        int result = x+y+add; // 计算结果
        sb.append(result % 10); // 将结果的个位数添加到结果中
        add = result/10; // 计算进位
        i--; // 移动指针
        j--; // 移动指针
    }
    return sb.reverse().toString(); // 将结果反转
}