本文共 2505 字，大约阅读时间需要 8 分钟。

思路：

LeetCode第11题

双指针有两种思路：

一种是两边往中间靠，另一种是两个指针一快一慢，从起点出发，当满足条件时

慢指针尝试接近快指针缩小范围获得最优解

class Solution {    public int maxArea(int[] height) {        int begin = 0;        int end = height.length-1;        int res = 0;        while(begin

下面也是两指针往中间靠的例子：

class Solution {    public int trap(int[] height) {                int res=0,left=0,recordLeft=0,right=height.length-1,recordRight=0;                        while(left
   
    recordLeft) {                    recordLeft = height[left];                }else{                    res+= recordLeft- height[left];//如果当前位置高度比前面记录的高度小，该地是一个坑，可以形成积水                                    }                left++;                                            }else{                if(height[right]>recordRight) {                    recordRight = height[right];                }else{                    res+=recordRight - height[right];                }                right--;                            }                    }        return res;            }}
   

很明显这是一个快慢指针的问题了，这里用了一个count变量来计数，另count等于 shortChars的长度，右边指针扫到shortChars的一个字母并且是第一次扫到，count数量减一，当count数量为0的时候说明【left,right】区间包含了整一个shortChars 这时尝试去移动 left指针，缩小区间去尝试获得最优解，此时当left扫过shortChars 的字母的时候，count的数量就要加1了，当count数量不为一的时候又要去移动right 指针去寻找解区间

当然网上另一种是另count=0，当right扫过shortChars 时count+1

class Solution {    public String minWindow(String s, String t) {        char[] longChars = s.toCharArray();        char[] shortChars = t.toCharArray();        int [] map = new int[128];        int left=0,flagLeft=0;        int right=0,flagRight=0;        int count = shortChars.length;        int minLen = Integer.MAX_VALUE;                        for(char c:shortChars)        {            map[c]++;        }                        while(right
   
    0) {                count--;            }            map[longChars[right]]--;            right++;                        while(count==0)            {                if(right-left
    
     0) {                    count++;                }                left++;            }                                            }        return minLen == Integer.MAX_VALUE ?"":s.substring(flagLeft,flagRight);                                    }}
    
   

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

由于java写这个代码不舒服，这里用一下C++ 的代码

class Solution {public:    int lengthOfLongestSubstring(string s) {                int freq[256] ={0};        int left=0;        int right=-1;        int res = 0;                while(left

总结一下快慢指针（滑动窗口的思想）

转载地址：http://tbyzi.baihongyu.com/