【Leetcode】滑动窗口

题目编号

3 209

3. 无重复字符的最长子串

解题思路

一开始以子串的长度为基准，发现循环中的代码非常复杂，一不注意就出错，后来看了评论才知道应该以左边的数字为基准，外层循环遍历整个字符串，内层循环遍历当前子串是否有相同的字符。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxCount = 0;
        int left = 0; // 左边的那个数
        char[] sToChar = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            for (int in = left; in < i; in++) {
                if (sToChar[in] == sToChar[i]) {
                    maxCount = Math.max(maxCount, i - left);
                    left = in + 1;
                    break;
                }
            }
        }
        maxCount = Math.max(maxCount, sToChar.length - left);
        return maxCount;
    }
}

209. 长度最小的子数组

解题思路

暴力破解法：

• 从第一个数开始往后加，加到满足条件看有几个元素，
• 从第二个数开始往后加，加到满足条件看有几个元素，然后跟第一个比较，
• 从第三个数开始往后加，加到满足条件看有几个元素，然后跟第二个比较，
• 。。。得出结果

代码

class Solution {
   public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length + 1;
        int i = 0;
        for (; i < nums.length; i++) {
            int right = i;
            int sum = 0;
            for (; right < nums.length; right++) {
                sum += nums[right];
                if (sum >= s) {
                    // 这里因为i已经加了1，但是right还没加1，所以得把1补过来
                    len = Math.min(len, right - i + 1);
                    break;
                }
            }
        }
        return len == nums.length + 1 ? 0 : len;
    }
}