数组

长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode） (leetcode-cn.com)

本题利用滑动窗口的思路来解决。可以将复杂度从O(n^n)降到O(n)。当然,continue的目的是为了防止Sum在调整之后，还是不满足条件，所以再加一个判断。

滑动窗口的思路，就是不断的调整子序列的初始位置和终止位置，适用于连续子序列问题。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0, j = 0;
        int end_i = nums.length;
        int result = nums.length + 1;
        int Sum = 0;
        int subLength;
        while (j <= end_i && i <= j) {

            if (Sum >= target) {
                subLength = (j - i);
                result = subLength < result ? subLength : result; //如果子序列和大于target且该序列更短，更新result的值
                Sum -= nums[i++]; //滑动窗口往前移一个
                continue; //滑动窗口之后，Sum的值发生变化，需要重新判断，此时应当再进行一轮判断而不是直接让右侧窗口进行滑动
            } //如果Sum<target，才进入下面的语句
            if ( j == nums.length) // 已经滑动到最右端了直接跳出循环
                break;
            Sum += nums[j++];//滑动窗口最右端右移一位
        }
        return result == nums.length + 1 ? 0 : result;
    }
}

904. 水果成篮 - 力扣（LeetCode） (leetcode-cn.com)

一把过的中等题目，快乐。

题目要求：选择一个最长的子序列，其中只包含两种元素。

思路：

本题采用，滑动窗口方法。使用basket1和basket2两个变量记录已经在篮子里的两个水果。j指向滑动窗口的最左侧，i指向滑动窗口的最右侧（即遍历指针）。

当窗口向右滑动时新进入窗口的元素，如果已经是在两个篮子里的种类，则更新窗口右侧的那种水果的起始位置。这里有点不好理解，如下所示：

[1, 3, 4, 5, 6, 7(1), 7(2), 8]

为了方便说明，我们给相同的元素编号。如果此时，6, 7(1), 7(2) 在滑动窗口内，则滑动窗口最右侧的元素是7，起始点就是7(1)。

当新进入滑动窗口的元素不是两个篮子里得元素，则滑动窗口里此时有了三种元素，应当进行一个更新。去掉滑动窗口靠左侧的元素。

依旧如上图所示，如果循环继续进行，滑动窗口向右滑动，把8纳入滑动窗口中，则滑动窗口此时有6,7,8三种元素，不符合滑动窗口只有两种元素的规定。因此，滑动窗口左侧需要向右移动，将6排除在外。因此，记录的7(1)，即元素7的开始位置就是下一步滑动窗口左侧应取得值。

每次滑动窗口更新之后，计算此时滑动窗口的长度，计算最大值。

// 本题要求，选择一个最长只有两个元素的子序列
class Solution {
    public int totalFruit(int[] fruits) {
        if(fruits.length == 1 && fruits.length == 2) {
            return fruits.length;
        }
        int basket1 = -1, basket2 = -1; //记录当前篮子里的水果
        int sum = 0;
        int curFruit = -1, curFruitLoc = 0; //记录当前的水果，和当前水果的起始位置
        int subSum = 0;
        int j = 0; // 记录篮子起始位置
        for (int i = 0; i < fruits.length; ++i) {
            if (fruits[i] == basket1 || fruits[i] == basket2)
            {
                if (fruits[i] != curFruit) {
                    // 记录在篮子里的连续最近，在更换篮子里水果的时候使用
                    curFruit = fruits[i];
                    curFruitLoc = i;
                }
            }
            
            else {
                j = curFruitLoc;
                curFruitLoc = i;
                if (basket1 == curFruit) { // 更新水果篮
                    basket2 = fruits[i];
                    curFruit = basket2;
                    
                }
                else {
                    basket1 = fruits[i];
                    curFruit = basket1;
                }
            }
                subSum = (i - j + 1); // 计算最长子序列
                sum = sum > subSum ? sum : subSum;
        }
        return sum;
    }
}

76. 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)

这个是独立解决的第一个hard难度的题目，呜呜呜，感觉有点兴奋。虽然最后通过的速度不算快，那也是过了！

class Solution {
    public String minWindow(String s, String t) {
        int t_len = 0; //用来记录匹配的元素的数量
        char s1[] = s.toCharArray();
        char t1[] = t.toCharArray();
        int need[] = new int[128];
        int loc_i = -1, loc_j= s.length() + 1; // 记录最终返回的位置，先取一个最大值
        int i,j;
        for (i =0; i<need.length; ++i) {
            need[i] = 0;
        }
        for (i = 0; i < t.length(); ++i) { //统计各个字符的起始位置
            need[t1[i]-'A']++;
        }
        for (i =0; i<need.length; ++i) { // 对 t_len进行初始化
            if (need[i] > 0)
                t_len++;
        }
        i = 0;
        for (j = 0; j < s.length(); ++j) { //j是右侧的滑动窗口
            if (t.contains(String.valueOf(s1[j]))) { // 如果当前的右侧窗口包括一个t里面的字串，进行窗口更新
                need[s1[j]-'A']--; //还需匹配的字符就少一个
                if (need[s1[j]-'A'] == 0) { //已经有一个字符匹配好了
                    t_len--;// 只在右侧窗口把一个字符匹配好之后t_len记录一次，后续无论窗口怎么移动，都不会改变当前的匹配情况
                }
                while (i < j) { // 更新左侧窗口位置
                    if (!t.contains(String.valueOf(s1[i]))) { //如果左侧窗口不是属于t的字符内，可以右移
                        ++i;
                    }
                    else if (need[s1[i]-'A'] < 0) { // 如果匹配次数过多，比如t中有3个A，但是已经匹配了四个，左侧窗口也可以右移
                        need[s1[i]-'A']++;
                        ++i;
                    }
                    else { //不是以上两种情况，不再移动左侧窗口
                        break;
                    }
                }
            }
            if (t_len == 0) {
                int temp_len = j - i;
                if (j - i < loc_j - loc_i) { // 新窗口更小
                    loc_j = j;
                    loc_i = i;
                }
            }
        }
        if (loc_i == -1)
            return "";
        return s.substring(loc_i,loc_j + 1);
    }

}

这个题的思路并不难，题目要求的解是字符串的某个连续子串，这就是一个典型的双指针问题。大概思路就是，每次右侧窗口向右移一格，就判断左侧窗口有没有碰见可以右移的新情况。在字符串左移之后，就判断当前的窗口长度是否比已经记录的字符长度更短，有一些小细节写在了注释里。