leetcode3

无重复的最长子串长度

开始的时候没有想出解法，后开看到了双指针滑动窗口的解法，其实这种处理方法很常见，将暴力求解的过程在一次循环中完成了，时间复杂度n。

class Solution
{
    public int lengthOfLongestSubstring(String s)
    {
        //简单的双指针滑动窗口
        int[] last=new int[128];//字符最后一次出现的位置
        for(int i=0;i<128;++i)last[i]=-1;//默认字符没有出现是-1,同时也为了防止改变start=0
        int start=0,n=s.length(),ans=0;//初始化
        for(int i=0;i<n;++i)//i进行滑动，带动start
        {
            int index=s.charAt(i);//强制转换成ASCII
            start=Math.max(start,last[index]+1);
            ans=Math.max(ans,i-start+1);
            last[index]=i;
        }
        return ans;
    }
}


这里需要注意一点，我开始差点没反应过来，start的更新一定要是start=Math.max(start,last[index]+1)，而不能是start=last[index]+1。

因为，start=last[index]+1，如果出现一个新字符的时候，start就会=0了，所以要用max限制它的左移动，这也正是滑动窗口的来源，从左到右一直滑动，找到最大的ans。

import java.util.*;

public class Solution
{
    public static void main(String args[])
    {
        System.out.println(lengthOfLongestSubstring("pwwkew"));
    }
    public static int lengthOfLongestSubstring(String s)
    {
        //简单的双指针滑动窗口
        int[] last=new int[128];//字符最后一次出现的位置
        for(int i=0;i<128;++i)last[i]=-1;//默认字符没有出现是-1,同时也为了防止改变start=0
        int start=0,n=s.length(),ans=0;//初始化
        for(int i=0;i<n;++i)//i进行滑动，带动start
        {
            int index=s.charAt(i);//强制转换成ASCII
            //start=Math.max(start,last[index]+1);
            start=last[index]+1;
            ans=Math.max(ans,i-start+1);
            last[index]=i;
            System.out.println((char)index+" "+start+" "+i);
        }
        return ans;
    }
}


碰到有点蒙的情况，当然是做debug了