本节内容

977.有序数组的平方
209.长度最小的子数组
59.螺旋矩阵II
总结

977.有序数组的平方※

题目建议：本题关键在于理解双指针思想

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep

题目分析

双指针，从两个方向向内查找，数值从后向前生成。两个指针比较自己的绝对值（或者平方）
结束条件：循环次数达到 N （或者左指针大于右指针）

方案一

双指针法

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0, right = nums.length -1;

        for (int i = right; i >= 0; i--) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                result[i] = nums[left] * nums[left];
                left++;
            } else {
                result[i] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:44 MB,击败了14.91% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html#%E5%8F%8C%E6%8C%87%E9%92%88%E6%B3%95

方案一

其于上述方案一致，具体代码请看方案一。

209.长度最小的子数组※

题目建议：本题关键在于理解滑动窗口，这个滑动窗口看文字讲解还挺难理解的，建议大家先看视频讲解。拓展题目可以先不做。

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解： https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

https://www.yuanql.top/2023/04/04/02_leetcode/209.%20%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/

题目分析

思考一：
尝试使用双指针找去除短板的方式去找最小的长度，但是其可能会导致去除的时候失去最小的长度，即在向内移动的时候失去了最优解。

思考二：
滑动窗口：
滑动窗口详解
使用滑动窗口可以从左向右进行遍历，这样就不会导致莫名失去最优的

方案一

class Solution {
    public int minSubArrayLen(int target, int[] nums) {

        int sum = 0, left = 0, right = 0, length = nums.length, flag = 0;

        while (sum < target) {
            if (right == length) {
                return flag;
            }
            sum += nums[right++];
        }

        flag = right - left;
        for (; right < length; right++) {
            sum += nums[right];
            while (true) {
                sum -= nums[left];
                if (sum < target) {
                    sum += nums[left];
                    break;
                }
                left++;
            }
            if (flag > (right - left + 1)) {
                flag = right - left + 1;
            }
        }

        // 特殊判断，此时窗口包含所有的数据
        if (flag == length) {
            while (true) {
                sum -= nums[left];
                if (sum < target) {
                    sum += nums[left];
                    break;
                }
                left++;
            }
            if (flag > (right - left)) {
                flag = right - left;
            }
        }
        return flag;
    }
}

以前做过的方案：
https://www.yuanql.top/2023/04/04/02_leetcode/209.%20%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/#%E8%87%AA%E5%B7%B1%E7%BC%96%E5%86%99

相同的思想，经过一段时间后，实现的具体逻辑就不同了，直接自己思考出的方案，距离最优的方案还是有区别的。

结果

解答成功:
执行耗时:1 ms,击败了99.80% 的Java用户
内存消耗:52 MB,击败了66.20% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

方案一：滑动窗口

在本题中实现滑动窗口，主要确定如下三点：

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？

窗口内：窗口内的所有数值相加大于 target；
起始位置：窗口内的数据大于 target 的时候，尝试左移，判断还是否大于 target ，一直移动知道无法在向左移动；
结束位置：遍历整个数组

class Solution {

    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

904. 水果成篮

官方题目链接： https://leetcode.cn/problems/fruit-into-baskets/

题目分析

滑动窗口，需要窗口之内的水果种类为2种，找出可以装下最多的水果个数等价于滑动窗口最大。

方案一

具体的思考逻辑可见代码的注释。

class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0,   // 滑动窗口的左测
                right = 1,  // 滑动窗口的右侧
                temp = left, // 下一次左侧窗口的落脚点
                flag = -1, // 判断当前滑动窗口中除了左侧，水果的种类 --> -1：代表当前只有一种水果，水果的种类是 left 所在的种类， 其他数值代表着其他的水果种类
                result = 1; // 滑动窗口的最大数值，也就是收集水果的 最大 数目。 
                            // 为什么写1呐： 当数组的长度为1的时候，其无法正常进入到下述循环中，所以默认数值设置为1用于解决数组长度为1的情况

        for (; right < fruits.length; right++) {
            // 此时 右侧的水果种类不等于左侧的水果种类
            if (fruits[right] != fruits[left]) {
                // 此时滑动窗口内只有一种水果
                if (flag == -1) {
                    flag = fruits[right]; // 直接将水果放入，进行下一轮循环
                    temp = right;
                } else { // 此时滑动窗口已经有两种水果了
                    if (fruits[right] == flag) { // 此时新加的水果种类依然属于其中的一种
                        if (fruits[right] != fruits[temp]) { // 此处用于判断temp的情况 001101  ，此时temp为0但是走到了1 这一步，就需要将temp更新为1
                            temp = right;
                        }
                    } else { // 此时有新的品种加入到了窗口中，需要收缩窗口，      并计算相关的数值
                        left = temp;
                        flag = fruits[right]; // 直接将水果放入，进行下一轮循环
                        temp = right;
                    }
                }
            } else { // 此处用于判断temp的情况 00110  ，此时temp为1但是走到了0 这一步，就需要将temp更新为0
                if (fruits[right] != fruits[temp]) {
                    temp = right;
                }
            }
            // 每次计算一轮，求解一次最大值
            if (result < (right - left + 1)) {
                result = right - left + 1;
            }
        }

        return result;
    }
}

结果

解答成功:
执行耗时:5 ms,击败了96.64% 的Java用户
内存消耗:54.5 MB,击败了6.61% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

官方题解 - 滑动窗口加哈希表

使用 Hash表，比上文中一顿判断猛如虎轻松的多，也更容易思考。

对于有多个种类需要进行区分的情况，可以考虑使用hash去做。

class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
            while (cnt.size() > 2) {
                cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
                if (cnt.get(fruits[left]) == 0) {
                    cnt.remove(fruits[left]);
                }
                ++left;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/fruit-into-baskets/solution/shui-guo-cheng-lan-by-leetcode-solution-1uyu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

76. 最小覆盖子串

官方题目链接： https://leetcode.cn/problems/minimum-window-substring/

题目分析

方法一：首先将字符串 t 中的所有数据放入到 HashMap，然后通过滑动窗口的方式去一步步减少HashMap中的数据，直到哈希表为空的时候，说明全部搞定，此时就记录一下其生成的字符串并对比。此方法时间复杂度较高。

方法二：在方法一的基础上进行优化，还是使用HaspMap存储字符串 t 的相关信息，滑动窗口的前进和缩小方式发生了改变。在方法一中，滑动窗口的缩小直接缩小到最左节点，此方法中拟采用左格逐步向右移动的方式来缩小滑动窗口。
设置一个标志位，用于记录HashMap中有多少个key对于的数值大于1，只要标志位flag大于1，则意味着目前滑动窗口中还未完全包含字符串 t 中的所有字符，在滑动窗口膨胀的过程中，允许HashMap在key对应的数值小于0，不再对key进行移除操作。
当标志位为0的时候，要对滑动窗口进行缩小，此时是判断HashMap在key对应的数值什么时候大于0，允许有一个数值大于0，即允许flag为1，但是不允许flag为2，当碰到flag将要变为2的时候，就要对滑动窗口进行扩大了。
在滑动窗口扩大和缩小的前夕，对滑动窗口内的字符串长度与结果中的字符串长度向对比，如果小于result的长度，则滑动窗口的数据覆盖result结果中的数据。

方案一

class Solution {
    public String minWindow(String s, String t) {
        int s_length = s.length(),  // 记录字符串 s 的长度
                t_length = t.length(),  // 记录字符串 t 的长度
                left = 0,   // 滑动窗口的左侧
                right = 0;  // 滑动窗口的右侧

        if (s_length < t_length) {
            return "";
        }

        if (s.equals(t)) {
            return s;
        }
        Boolean flag = false; // 用于判断滑动窗口是否正在扩大,

        StringBuffer result = new StringBuffer(),  // 最终的返回内容
                resultTemp = new StringBuffer(); // 用于记录中间的产生的字符串

        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        for (int i = 0; i < t_length; i++) {
            hashMap.put(t.charAt(i), hashMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        HashMap<Character, Integer> clonMap = new HashMap<>(hashMap);  // 浅拷贝

        for (; right < s_length; right++) {
            if (clonMap.containsKey(s.charAt(right))) {
                if (!flag) {
                    flag = true;
                    left = right;
                }
                if (clonMap.get(s.charAt(right)) == 1) {
                    clonMap.remove(s.charAt(right));
                } else {
                    clonMap.put(s.charAt(right), clonMap.get(s.charAt(right)) - 1);
                }
                if (clonMap.isEmpty()) { // 此时已经找到全部t中的参数，需要对其进行相关的处理
                    resultTemp.append(s.charAt(right));
                    if (result.length() > resultTemp.length() || result.length() == 0 ) {
                        result = resultTemp;
                    }
                    resultTemp = new StringBuffer();
                    right = left; // 此处需注意，不能使用++left，因为现在在循环中，下一步就会到达此处
                    flag =  false;
                    clonMap = new HashMap<>(hashMap);
                }
            }

            if (flag) { // 当滑动窗口开始扩大的时候，所有相关的字符串都要放入其中
                resultTemp.append(s.charAt(right));
            }

        }

        return result.toString();
    }
}

结果

运行超时
265 / 267 个通过测试用例

分析

时间复杂度：
O( n * n ) <– 极端情况下

空间复杂度：
O( n ) <– 极端情况下

方案二

在方案一的基础上进行优化，还是使用HaspMap存储字符串 t 的相关信息，滑动窗口的前进和缩小方式发生了改变。在方法一中，滑动窗口的缩小直接缩小到最左节点，此方法中拟采用左格逐步向右移动的方式来缩小滑动窗口。
设置一个标志位，用于记录HashMap中有多少个key对于的数值大于1，只要标志位flag大于1，则意味着目前滑动窗口中还未完全包含字符串 t 中的所有字符，在滑动窗口膨胀的过程中，允许HashMap在key对应的数值小于0，不再对key进行移除操作。
当标志位为0的时候，要对滑动窗口进行缩小，此时是判断HashMap在key对应的数值什么时候大于0，允许有一个数值大于0，即允许flag为1，但是不允许flag为2，当碰到flag将要变为2的时候，就要对滑动窗口进行扩大了。
在滑动窗口扩大和缩小的前夕，对滑动窗口内的字符串长度与结果中的字符串长度向对比，如果小于result的长度，则滑动窗口的数据覆盖result结果中的数据。

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        if (s.equals(t)){
            return s;
        }

        HashMap<Character, Integer> tHashMap = new HashMap<Character, Integer>(); // 记录字符串 t 的字符情况

        for (int i = 0; i < t.length(); i++) {  // 将字符串 t 拆分成一个个字符，放入到HashMap中
            tHashMap.put(t.charAt(i), tHashMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        StringBuilder result = null,  // 最终的返回数值
                temp = new StringBuilder(); // 记录字符数组的中间变量
        int left = 0, // 滑动窗口的左节点，用于窗口收缩
                right = 0, // 滑动窗口的右节点，用于窗口扩大
                tFlag = tHashMap.size(); // 记录HashMap中数值大于 0 的情况

        for (; right < s.length(); right++) { // 此层只用于扩大，所有在其内容去写
            if (tHashMap.containsKey(s.charAt(right))) {
                tHashMap.put(s.charAt(right), tHashMap.get(s.charAt(right)) - 1);
                if (tHashMap.get(s.charAt(right)) == 0) { // 每当有一个数值减到0的时候，就将标志位减一
                    tFlag--;
                }
                if (tFlag == 0) { // 此时需要对滑动窗口进行收缩了
                    temp.append(s.charAt(right)); // 先将最右侧所看到的数据注入进来

                    if (result == null || result.length() > temp.length()) { // 对结果进行更新
                        result = new StringBuilder(temp);
                    }

                    // 正式开始进行窗口收缩
                    while (tFlag == 0 || tFlag == 1) {
                        if (tHashMap.containsKey(s.charAt(left))) {
                            tHashMap.put(s.charAt(left), tHashMap.get(s.charAt(left))  + 1);
                            if (tHashMap.get(s.charAt(left)) == 1) {
                                tFlag++; // 此时窗口中刚刚好不能装下相关的数据，但是目前他temp中的数据刚刚好，所有此时可以更新result
                                if (tFlag == 1 && result.length() > temp.length()) { // 对结果进行更新
                                    result = new StringBuilder(temp);
                                }
                            } else if (tHashMap.get(s.charAt(left)) == 2) { // 此时说明一个字符串尝试弹出去两次，这是不被允许的，直接break
                                left++;
                                tFlag++;
                                if (temp.length() > 1) {
                                    temp.deleteCharAt(0);
                                } else {
                                    temp.deleteCharAt(0);
                                    break;
                                }
                                break;
                            }
                        }
                        left++;
                        if (temp.length() > 1) {
                            temp.deleteCharAt(0);
                        } else {
                            temp.deleteCharAt(0);
                            break;
                        }
                    }

                    // 因为相关数据删多了，需要重新补回来
                    left--;
                    temp.insert(0, s.charAt(left));
                    tHashMap.put(s.charAt(left), tHashMap.get(s.charAt(left)) - 1);
                    tFlag--;

                    temp.deleteCharAt(temp.length() - 1);
                }
            }
            temp.append(s.charAt(right));
        }
        
        return result == null ? "" : result.toString();
    }
}

结果

解答成功:
执行耗时:44 ms,击败了34.25% 的Java用户
内存消耗:44.3 MB,击败了5.03% 的Java用户

分析

时间复杂度：
O( n + m )

空间复杂度：
O( m + n ) <– 极端情况下

官方题解

https://leetcode.cn/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/

class Solution {
    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check() {
        Iterator iter = ori.entrySet().iterator(); 
        while (iter.hasNext()) { 
            Map.Entry entry = (Map.Entry) iter.next(); 
            Character key = (Character) entry.getKey(); 
            Integer val = (Integer) entry.getValue(); 
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        } 
        return true;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

59.螺旋矩阵II※

题目建议：本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

题目分析

思考一：
定义参数：
flage = 0, // 定义下一步加入数据的前进方向，0：向右 1：向下 2：向左 3：向上
up = 1, // 上节点的阈值
down = n - 1, // 下节点的阈值
left = 0, //左节点的阈值
right = n - 1, // 右节点的阈值
x = 0, // 当前所在节点的 x 轴坐标
y = 0; // 当前所在节点的 y 轴坐标

循环螺旋判断。

方案一

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ints = new int[n][n];
        int flage = 0,  // 定义下一步加入数据的前进方向，0：向右   1：向下   2：向左   3：向上
                up = 1,     // 上节点的阈值
                down = n - 1,   // 下节点的阈值
                left = 0,   //左节点的阈值
                right = n - 1,  // 右节点的阈值
                x = 0,  // 当前所在节点的 x 轴坐标
                y = 0;  // 当前所在节点的 y 轴坐标

        for (int i = 1; i <= n * n; i++) {
            ints[x][y] = i;
            switch (flage) {
                case 0:
                    if (y == right) {
                        flage = 1;
                        x++;
                        right--;
                    } else {
                        y++;
                    }
                    break;
                case 1:
                    if (x == down) {
                        flage = 2;
                        y--;
                        down--;
                    } else {
                        x++;
                    }
                    break;
                case 2:
                    if (y == left) {
                        flage = 3;
                        x--;
                        left++;
                    } else {
                        y--;
                    }
                    break;
                case 3:
                    if (x == up) {
                        flage = 0;
                        y++;
                        up++;
                    } else {
                        x--;
                    }
                    break;
            }
        }
        return ints;
    }
}

曾经的做法：
https://www.yuanql.top/2023/04/13/02_leetcode/59.%20%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5%20II/

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39 MB,击败了99.52% 的Java用户

分析

时间复杂度：
O( n * n )

空间复杂度：
O( n * n )

代码随想录

https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

方案一

这道题目可以说在面试中出现频率较高的题目，本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;  // 控制循环次数
        int[][] res = new int[n][n];
        int start = 0;  // 每次循环的开始点(start, start)
        int count = 1;  // 定义填充数字
        int i, j;

        while (loop++ < n / 2) { // 判断边界后，loop从1开始
            // 模拟上侧从左到右
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }

            // 模拟右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }

            // 模拟下侧从右到左
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }

            // 模拟左侧从下到上
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++;
        }

        if (n % 2 == 1) {
            res[start][start] = count;
        }

        return res;
    }
}

54. 螺旋矩阵

#未完成

官方题目链接： https://leetcode.cn/problems/spiral-matrix/

题目分析

方案一

结果

分析

时间复杂度：
O( )

空间复杂度：
O( )

方案二

结果

分析

时间复杂度：
O( )

空间复杂度：
O( )

总结※

题目建议：希望大家也做一个自己对数组专题的总结

文章链接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html

数组常用到的算法

二分法

二分法的使用条件：
见到有顺序的数组（有些无序的数组也可以通过排序变成有序的），就要想到是否可以使用二分法，都来碰碰瓷。但是当数组中有重复数据的时候，，二分查找返回的数据将是不唯一的，所以此时要慎用二分法。

双指针法

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。

滑动窗口

其属于双指针法的变种。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

02、第一章数组part02

http://yuanql.top/2023/07/13/02_1_代码随想录算法训练营18期/02、第一章数组part02/

作者

Qingli Yuan

发布于

2023年7月13日

许可协议

03、第二章链表part01 上一篇

01、第一章数组part01 下一篇

02、第一章 数组part02

本节内容

977.有序数组的平方※

题目分析

方案一

结果

分析

代码随想录

方案一

209.长度最小的子数组※

题目分析

方案一

结果

分析

代码随想录

方案一：滑动窗口

904. 水果成篮

题目分析

方案一

结果

分析

官方题解 - 滑动窗口加哈希表

76. 最小覆盖子串

题目分析

方案一

结果

分析

方案二

结果

分析

官方题解

59.螺旋矩阵II※

题目分析

方案一

结果

分析

代码随想录

方案一

54. 螺旋矩阵

题目分析

方案一

结果

分析

方案二

结果

分析

总结※

数组常用到的算法

二分法

双指针法

滑动窗口

02、第一章数组part02