双指针问题

采用双指针解法的题目大致可以分为两类，一类是二分，一类是滑动窗口

二分

leetcode162 寻找峰值

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left+(right-left)/2;
            if(nums[mid] < nums[mid+1]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }

        return left;
    }
}

leetcode33 搜索旋转排序数组

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[left] <= nums[mid]){
                if(nums[mid] < target ||nums[left] > target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }else{
                if(target > nums[right] || target < nums[mid]){
                    right = mid-1;
                }else{
                    left = mid +1;
                }
            }
        }
        return -1;
    }
}

leetcode875 爱吃香蕉的珂珂

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int min = 1;
        int max = 0;
        for(int i:piles){
            if(i>max){
                max = i;
            }
        }
        int k = max;
        while(min < max){
            int speed = min +(max-min)/2;
            int time = get_time(piles,speed);
            if(time <= h){
                k = speed;
                max = speed;
            }else{
                min = speed+1;
            }
        }

        return k;
    }

    public int get_time(int[] piles,int speed){
        int res = 0;
        for(int i:piles){
            if(i%speed == 0){
                res+=i/speed;
            }else{
                res+=i/speed+1;
            }
        }
        return res;
    }
}

滑动窗口

leetcode3 无重复字符最长字串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <=1){
            return s.length();
        }
        int n = s.length();
        int[] freq = new int[128];
        int left = -1;
        int right = 0;
        int max = 0;
        while(left<right &&right<n){
            if(freq[s.charAt(right)] == 0){
                freq[s.charAt(right)]++;
                right++;
            }else{
                left++;
                freq[s.charAt(left)]=0;
            }
            max = Math.max(max,right-left-1);
        }

        return max;
    }
}

leetcode209 长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int n = nums.length;
        int left = 0;
        int right = 0;
        int current_sum = nums[0];
        while(right<n){
            if(current_sum >= target){
                res = Math.min(res,right-left+1);
                current_sum -=nums[left];
                left++;
            }else{
                right++;
                if(right>=n){
                    break;
                }
                current_sum+=nums[right];
            }
        }

        return res==Integer.MAX_VALUE?0:res;
    }
}