算法：【双指针算法】(待完善)

双指针算法

模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

1.最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10000000;

        // 枚举 a
        for (int i = 0; i < n; ++i) {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                // 根据差值的绝对值来更新答案
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    // 如果和大于 target，移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target，移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
}

2.盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        // 双指针法
        if(height == null || height.length == 0)
            return 0;
        int i=0, j=height.length-1;
        int res = 0;
        int curarea = 0;
        while(i <= j){
            if(height[i] <= height[j]){
                curarea = (j-i)*height[i];
                i++;
            }else{
                curarea = (j-i)*height[j];
                j--;
            }
            res = Math.max(curarea, res);
        }
        return res;
    }   
}

3.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

class Solution {
    // 双指针法
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length == 0)
            return res;
        int n = nums.length;
        Arrays.sort(nums);
        for(int i=0; i<n; i++){
            if(i>0 && nums[i] == nums[i-1])
                continue;
            int j=i+1, k=n-1;
            while(j<k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0){
                    System.out.println("....");
                    List<Integer> tmp = new LinkedList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    tmp.add(nums[k]);
                    res.add(tmp);
                }
                if(sum > 0){
                    int k0 = k-1;
                    while(j<k0 && nums[k0] == nums[k])
                        k0--;
                    k = k0;
                }else{
                    int j0 = j+1;
                    while(j0<k && nums[j0] == nums[j])
                        j0++;
                    j = j0;
                }
            }
        }
        return res;
    }
}

4.验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

输入: "A man, a plan, a canal: Panama"
输出: true

class Solution {
    // 1.暴力+栈(可以用StringBUilder来代替栈)
    // public boolean isPalindrome(String s) {
        // char[] chs = s.toCharArray();
        // int n = chs.length;
        // Deque<Character> stack = new LinkedList<>();
        // for(int i=0; i<n; i++){
        //     if(Character.isDigit(chs[i]) || Character.isLetter(chs[i]))
        //         stack.push(chs[i]);
        // }
        // for(int i=0; i<n; i++){
        //     if(Character.isDigit(chs[i]) || Character.isLetter(chs[i])){
        //         char ch = stack.pop();
        //         ch = ch > chs[i] ? Character.toUpperCase(ch) : ch == chs[i] ? ch : Character.toLowerCase(ch);
        //         if(ch !=  chs[i])
        //             return false;
        //     }
        // }
        // return true;
    // }

    // 2.双指针法
    public boolean isPalindrome(String s) {
        char[] chs = s.toCharArray();
        int left = 0, right = chs.length-1;
        while(left < right){
            while(left < right && !Character.isLetterOrDigit(chs[left]))
                left++;
            while(left < right && !Character.isLetterOrDigit(chs[right]))
                right--;
            if(left < right){
                if(Character.toLowerCase(chs[left]) != Character.toLowerCase(chs[right]))
                    return false;
                left++;
                right--;
            }
        }
        return true;
    }
}