Leetcode（经典题）day3-双指针

 验证回文串

125. 验证回文串 - 力扣（LeetCode）

直接双指针对比就行。

public boolean isPalindrome(String s) {
        char[] arr = s.toLowerCase().toCharArray();
        int l=0,r=arr.length-1;
        while(l<r){
            while (l<r&&!ischar(arr[l])){
                l++;
            }
            while (l<r&&!ischar(arr[r])){
                r--;
            }
            if (arr[l++]!=arr[r--]){
                return false;
            }
        }
        return true;
 
        }
    public boolean ischar(char c){
        return (c>='0'&&c<='9')||(c>='a'&&c<='z');
    }

判断子序列 

392. 判断子序列 - 力扣（LeetCode）

同样使用双指针。

    public boolean isSubsequence(String s, String t) {
        int slow=0;
        int fast=0;
        while(fast<t.length()&&slow<s.length()){
            if(s.charAt(slow)==t.charAt(fast)){
                slow++;
            }
            fast++;
        }
        if(slow==s.length()){
            return true;
        }
        return false;
    }

两数之和|| 

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

使用双指针，一个从头，一个从尾，如果当前值比target小，头指针++，如果当前值比target大，尾指针--

    public int[] twoSum(int[] numbers, int target) {
        int l=0,r=numbers.length-1;
        while(l<r){
            int res = numbers[l]+numbers[r];
            if(res == target){
                return new int[]{l+1,r+1};
            }else if(res > target){
                r--;
            }else{
                l++;
            }
        }
        return null;
    }

 盛水最多的容器

11. 盛最多水的容器 - 力扣（LeetCode）

双指针，一个从头，一个从尾，每次比较两个指针当前的所指的值，头指针小，则头指针++，尾指针小，则尾指针--，同时计算当前的面积并更新最大值。

    public int maxArea(int[] height) {
        int n = height.length;
        int left=0;
        int right=n-1;
        int max=(right-left)*Math.min(height[left],height[right]);
        while(left<right){
            if(height[left]<height[right]){
                left++;
            }else{
                right--;
            }
            int index = (right-left)*Math.min(height[left],height[right]);
            if(max<index){
                max=index;
            }
        }
        return max;
    }

三数之和

15. 三数之和 - 力扣（LeetCode）

与二数之和原理一致，多加了去重处理。

        if (nums.length<3){
            return null;
        }
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int i=0;
        int j,k;
        while (i<nums.length-2){
            j=i+1;
            k=nums.length-1;
            while(j<k){
                if(nums[j]+nums[k]+nums[i]==0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    res.add(list);
                    while(j<k&&nums[j+1]==nums[j]) {
                        j++;
                    };
                    while(j<k&&nums[k-1]==nums[k]) {
                        k--;
                    };
                    j++;
                    k--;
                }else if(nums[j]+nums[k]+nums[i]>0){
                    k--;
                }else {
                    j++;
                }
            }
            while (i<nums.length-2&&nums[i]==nums[i+1]){
                i++;
            }
            i++;
        }
        return res;
    }