Sliding Window

Abstract：leetcode sliding window专题

面试题57 - II. 和为s的连续正数序列[Easy]

解法一：滑动窗口

说实话这题最蛋疼的是返回类型，要是没参考dalao的题解，我都还不会List<int[]>转二维数组

• 标准的滑动窗口题：如果大了左边界++，如果小了右边界++，如果正好则记录答案
• 直接贴解法，很直观了

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list=new ArrayList<int[]>();
        int lo=1,hi=1,sum=0;
        while(lo<=target/2 ){ //lo最多等于target/2
            if(sum<target){   
                sum+=hi++;    //右边界++
            }
            else if(sum>target){
                sum-=lo++;    //左边界++，sum回溯
            }
            else{               //有解
                int[] ans=new int[hi-lo];
                for(int i=0;i<hi-lo;i++)ans[i]=i+lo;
                list.add(ans);
                sum-=lo++;      //记录解之后左边界++，sum回溯
            }
        }
        return list.toArray(new int[list.size()][]); //转回二维数组
    }
}

3. Longest Substring Without Repeating Characters[Medium]

解法一：HashSet滑动窗口

同样是标准的滑动窗口，当遇到重复时，remove左边

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int i=0, j=0,len=0;
        while (i<n && j<n) {
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));      //没重复，继续向右
                len = Math.max(len, j - i);  //更新len  
            }
            else {
                set.remove(s.charAt(i++));     //remove左边
            }
        }
        return len;
    }
}