CSDN话题挑战赛第2期
参赛话题：算法题解

1、leetcode977. 有序数组的平方

1.题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

2.题目链接

https://leetcode.cn/problems/squares-of-a-sorted-array/

3.思路讲解

3.1 易错/没思路原因

错误分析1：非递减数组，没想到负数在平方后是前大后小，正数在平方后也是前小后大，所以最大值一定在两端，所以可以相向双指针来找当前的最大值，开辟一个新数组来记录，最后逆置即可

代码实现细节：
1-终止下标是nums.size() - 1，别忘记-1
2-下标在每轮循环结束后记得改变

3.2 多方法

• 代码优化：
  1-防止vector扩容消耗，可以提前resize或调用带参构造函数，在每轮循环存数据时，未提前开辟的数组用push_back()，而提前开辟空间可以用v[尾下标–]；

3.3 难点/核心点

1. 数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
2. 可以定义一个新数组result，来作为返回值。

4.模板代码

vector<int> sortedSquares(vector<int>& nums) 
    {
        // 前提：非递减顺序排序的整数数组；1 <= nums.length
        // 思路：1-明确非递减顺序数组；2-观察到如果数组有负数，平方后数组前后为最大值，中间为小值，思考到用相向双指针来取当前最大值，可以放在新数组中，最后逆置即可。(优化：如果提前开辟空间，可以直接从后往前存储数据，无需逆置)
        
        for (auto& e : nums)
        {
            e = e * e;
        }

        vector<int> res;
        int l = 0;
        int r = nums.size() - 1;
        while (l <= r)
        {
            if (nums[l] > nums[r])
            {
                res.push_back(nums[l++]);
            }
            else
            {
                res.push_back(nums[r--]);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }

5.算法与时间复杂度

时间（o(log n)）（遍历查找）
空间（o(1)）

6.感想

1. 1-明确非递减顺序数组；
2. 2-观察到如果数组有负数，平方后数组前后为最大值，中间为小值，思考到用相向双指针来取当前最大值；
3. 3-可以放在新数组中，最后逆置即可。(优化：如果提前开辟空间，可以直接从后往前存储数据，无需逆置)

2、leetcode209. 长度最小的子数组

1.题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

2.题目链接

https://leetcode.cn/problems/minimum-size-subarray-sum/

3.思路讲解

3.1 易错/没思路原因

对滑动窗口使用不敏感

3.2 多方法

• 最小滑动窗口：

• 最大滑动窗口：
  

3.3 难点/核心点

1. 滑动窗口的妙处：

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

2. 滑动窗口的核心：

4.模板代码

int minSubArrayLen(int target, vector<int>& nums) 
    {
        // 前提：1 <= nums.length
        // 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法
        // 思路：求最小滑动数组，i作为窗口起始下标，j作为窗口结束下标

        int len = INT_MAX;
        int sum = 0;
        for (size_t i = 0, j = 0; j < nums.size(); j++)
        {
            // 将j位置的元素纳入滑动数组
            sum += nums[j];

            // j后移的同时，i也后移缩小滑动窗口，可以并入while中

            // 满足要求后，缩小滑动窗口
            while (sum >= target)
            {
                // 记录并判断当前长度
                len = (j - i + 1) < len ? (j - i + 1) : len;

                // 缩小滑动窗口
                sum -= nums[i++];
            }
        }
        return INT_MAX == len ? 0 : len;
    }

5.算法与时间复杂度

时间（o(n)）（遍历查找）
空间（o(1)）

6.感想

• 套用滑动窗口的模板

总结

真💙欢迎各位给予我更好的建议，小编创作不易，觉得有用可以大拇指鼓励哦，感谢大家。peace
希望大家一起坚持学习，共同进步。梦想一旦被付诸行动，就会变得神圣。

欢迎各位大佬批评建议，分享更好的方法！！！🙊🙊🙊