Day 2 数组：977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day 2 数组：977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

代码随想录算法训练营Day2 数组：977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ

在 C++ 标准库中，std::sort函数用于对一个序列进行排序。其底层实现可能会依赖于编译器和库的实现，但通常，它基于一种称为 IntroSort 的混合排序算法，该算法是 QuickSort、HeapSort 和 InsertionSort 的混合体。

快速排序 (QuickSort) 是 std::sort 的主要算法，它是一种高效的、在平均情况下具有 O(n log n) 时间复杂度的排序算法。但是在最坏情况下（例如当输入序列已经排序或接近排序时），快速排序的时间复杂度会变为 O(n^2)。

为了避免这种最坏情况，std::sort 利用了 IntroSort 的策略。当排序的递归深度超过一个阈值时（通常是 log2(n)），IntroSort 切换到堆排序 (HeapSort)。堆排序的时间复杂度始终是 O(n log n)，但其常数因子使其在小数组或近乎排序的输入上表现较差。

对于非常小的数组，IntroSort 会使用插入排序 (InsertionSort)，因为在小数组上，插入排序的性能可能优于快速排序或堆排序。

因此，总的来说，std::sort 的平均时间复杂度和最坏情况时间复杂度都是 O(n log n)，并且对于各种输入，都能保持良好的性能。

双指针解法

数组其实是有序的，暴力解法并没有利用到这一特点。

由于负数的存在，负数平方之后可能就会成为最大数，因此数组平方后的最大值就应该在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法，i指向起始位置，j指向终止位置。

定义一个新的数组result来装进行平方之后的数组元素。（新数组result，和A数组一样的大小，让k指向result数组终止位置。）

定义一个索引下标，k = nums.size() - 1; 下标k的作用：新的数组要从大到小来更新。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

如动画所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-myL9Fnm1-1685501676860)(https://code-thinking.cdn.bcebos.com/gifs/977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.gif)]

因为每次取的时候都是取了一个最大值（两头向中间取，先取最大，再取次大）。

这样的话，更新result数组也要下标由大到小来更新，最后得到的这个result数组才是一个按非递减顺序排序（元素从小到大）的集合。

while循环终止的条件：只要 i <= j 就继续执行该循环

⚠️注意：

Q:若只写i < j 会怎样？

A:那我们就把i和j相等的时候指向的这个元素给落下了，我们还得将这个元素放到result数组中。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result (nums);
        int k = nums.size() - 1;
        int i = 0;
        int j = nums.size() - 1;
        while(i <= j)  // 注意这里要i <= j，因为最后要处理两个元素
        {
            if(nums[i] * nums[i] > nums[j] * nums[j])
                result[k--] = nums[i] * nums[i],i++;
            else
                result[k--] = nums[j] * nums[j],j--;
        }
        return result;
    }
};

时间复杂度： $O(\ n)$
空间复杂度： $O (1)$

此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。

209.长度最小的子数组

题目链接

💡思路

暴力解法

这道题目暴力解法当然是两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)。

代码如下:

// 本人写法
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {     
        int min = 0; // 最终的结果
        
        for(int i = 0;i < nums.size();i++)  // 设置子序列起点为i
        {
            int sum = nums[i];
            if (sum >= target) return 1; // 若取的nums[i]刚好大于或者等于target，就说明子序列只有1个元素，因此返回长度 1  
            for(int j = i + 1;j <nums.size() ;j++) // 设置子序列终止位置为j ，前面已经将numsp[i]赋值给sum，因此j从 i + 1开始遍历 
            {
                int tmp = min;  
                sum += nums[j];
               if(sum >= target)  // 一旦发现子序列和超过了s，更新min
               {
                    min = j - i + 1; // 取子序列的长度
                    if (tmp != 0 )  // 因为min 初始化为 0 ，所以min第一次赋值时，min不和初始化的min比较。因此只有上一次不等于0时，才更新min
                    {
                        min = min<tmp? min:tmp;
                    }
             
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
               }
              
            }
        }

        return min; // 若没有找到，则返回0 (min初始化为0) ，若找到了，则返回min(最小子序列的长度)
    }
};

// 优化写法
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

时间复杂度： $O(\ n^2)$
空间复杂度： $O (1)$

后面力扣更新了数据，暴力解法已经超时了。

力扣最后一个用例，显示超时：

Day 2 数组：977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ

我们点击查看全部，发现用例大的离谱

Day 2 数组：977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ

滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来做2个for循环所做的事情。

首先要思考如果用一个for循环，那么应该表示滑动窗口的起始位置，还是终止位置。

⚠️注意：

这个索引下标 j 表示的究竟是滑动窗口里面的终止位置还是起始位置？

可以先假设 j 表示的是起始位置，

若 j 表示的是起始位置，这个for循环一次一次把索引下标向后移动，这个终止位置要把后面所有的元素遍历一遍，才能返回所有以这个起始 i 为起始位置的集合，然后我们再去判断这个集合里面的所有元素: 如果 >= target，去搜集所有 >= target这些集合里面的所有的长度，再取一个最小的。如果终止位置是一个一个向后移动的话，那么这个方法和暴力的解法是一样的。所以如果这一个for循环里面的这个j表示的是起始位置的话，那终止位置依然要把所有位置都遍历一遍，那么它的思路就和暴力是一样的。

因此这一个for循环里面的j一定指向的是终止位置，而起始位置需要我们用动态移动的策略来移动起始位置，这样才能用一个for循环的思路来解决这道题。

如果只用一个for循环来表示滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入暴力解法的怪圈。

所以只用一个for循环，那么这个循环的索引，一定是表示滑动窗口的终止位置。

那么问题来了，滑动窗口的起始位置如何移动呢？

这里还是以题目中的示例来举例，s=7，数组是 2，3，1，2，4，3，来看一下查找的过程：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jUmtbKrt-1685501676864)(https://code-thinking.cdn.bcebos.com/gifs/209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.gif)]

最后找到 4，3 是最短距离。

其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

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

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

窗口就是满足其和 ≥ s 的长度最小的连续子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了（题目给定一个含有 n 个正整数的数组），窗口就要向前移动了（也就是该缩小了），所以窗口向前移动一次且要缩小（滑动窗口内元素的总和要先减去nums[i]（即sum = sum - nums[i]）,并且将索引i要加1（即i = i + 1））

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引j。

解题的关键在于窗口的起始位置如何移动，如图所示：

Day 2 数组：977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ

⚠️注意：

如何定义滑动窗口?

左闭右闭区间

start: 窗口起始
end: 窗口结束
窗口: [start,end]构成的闭区间

那么, 我们考虑一下start和end取值的意义:

start < end: 不必说
start == end: 窗口只含有1个元素
start > end: 窗口为空（也就是说出现start > end(其实只有start = end+1), 是无需害怕的

代码如下:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int start = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int end = 0; end < nums.size(); end++) {// 左闭右开区间  end为窗口结束， end的最大值为nums.size - 1 窗口: [start,end] 开始时 [0,0]
            sum += nums[end];
            // 注意这里使用while，每次更新 start（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (end - start + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[start++]; // 这里体现出滑动窗口的精髓之处，不断变更start（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

时间复杂度： $O(\ n)$
空间复杂度： $O (1)$

左闭右开区间

start: 窗口起始
end: 窗口结束下一个
窗口: [start,end)构成的闭区间

那么, 我们考虑一下start和end取值的意义:

start < end-1: 不必说
start == end - 1: 窗口只含有1个元素
start == end: 窗口为空

代码如下:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int start = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int end = 1; end <= nums.size(); end++) { // 左闭右开区间  end为窗口结束下一个，end的最大值为nums.size() 窗口: [start,end) 开始 [0,1)
            sum += nums[end-1]; // 要从第一个元素开始判断
            // 注意这里使用while，每次更新 start（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (end - start); // 取子序列的长度 因为end是窗口结束位置的下一个，所以end - start是窗口的长度
                result = result < subLength ? result : subLength;
                sum -= nums[start++]; // 这里体现出滑动窗口的精髓之处，不断变更start（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

时间复杂度： $O(\ n)$
空间复杂度： $O (1)$

⚠️注意：

为什么时间复杂度是O(n)。

不能以为for里放一个while就是 $O(\ n)$ ，主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是 $O(\ n)$ 。

解释:

假设我们有一个长度为 n 的数组，我们需要遍历数组寻找满足条件的最短子序列。滑动窗口法的思路就是用两个指针（start和end）来定义一个窗口，然后滑动这个窗口来检查窗口内的元素。

在算法中，每个元素最多被访问两次：一次是当窗口向右扩大（end向右移动）包含更多元素时，另一次是当窗口向右缩小（start向右移动）排除一些元素时。因此，整个算法的时间复杂度就是 $O (2 n)$ ，也就是 $O (n)$ 。

具体来说，滑动窗口的算法中，start 和 end 指针都只会从左向右移动，而且每个指针都只会移动 n 次（n 是数组的长度）。start 指针每次移动时会减少窗口的和，end 指针每次移动时会增加窗口的和。因此，总共的操作数是 2n，所以时间复杂度是 $O (n)$ 。

空间复杂度，因为我们只需要几个变量来存储当前的和、start和end的位置，以及当前最小的子序列长度，这些都是常数空间，所以空间复杂度是 $O (1)$ 。

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

59.螺旋矩阵Ⅱ

题目链接

💡思路

补充vector数组语法

C++中的std::vector是一种动态数组，提供了很多强大的功能。以下是一些基本的std::vector使用方法：

创建vector：

std::vector<int> vec; // 创建一个空的int型vector
std::vector<int> vec(10); // 创建一个包含10个元素的int型vector，每个元素都初始化为0
std::vector<int> vec(10, 1); // 创建一个包含10个元素的int型vector，每个元素都初始化为1
std::vector<std::vector<int>> vec2d(10, std::vector<int>(10, 0)); // 创建一个10x10的二维int型vector，所有元素都初始化为0

添加元素：

vec.push_back(5); // 在vec的末尾添加一个元素5

访问元素：

int first = vec[0]; // 访问第一个元素
int first = vec.at(0); // 访问第一个元素（安全访问，如果索引超出范围，会抛出异常）

修改元素：

vec[0] = 10; // 修改第一个元素的值为10
vec.at(0) = 10; // 修改第一个元素的值为10（安全访问，如果索引超出范围，会抛出异常）

获取vector的大小：

int size = vec.size(); // 获取vec中的元素数量

删除元素：

vec.pop_back(); // 删除vec的最后一个元素
vec.erase(vec.begin() + 5); // 删除第6个元素（索引从0开始）
vec.erase(vec.begin(), vec.begin() + 5); // 删除前5个元素

erase函数会真正地从std::vector中删除元素。删除后，该元素后面的所有元素都将向前移动以填补空位，这可能涉及内存的重新分配。因此，erase操作可能是一个时间复杂度为O(n)的操作，其中n是std::vector中的元素数量。因此，在频繁使用erase操作时，需要考虑其可能带来的性能影响。

如果你只想快速地移除一个元素，而不关心元素的顺序，你可以考虑将要删除的元素与最后一个元素交换，然后调用pop_back。这样，你就可以在常数时间内删除一个元素，但这会改变元素的顺序。

当你使用erase方法时，比如你有一个vector如下：

std::vector<int> vec = {1, 2, 3, 4, 5};

现在你想删除第三个元素(即3)，你可以这样做：

vec.erase(vec.begin() + 2);

结果是：

vec = {1, 2, 4, 5};

你可以看到，3被删除了，其后面的元素4和5都向前移动了一个位置。

然而，如果你不关心元素的顺序，只想快速删除一个元素，你可以这样做：

std::swap(vec[2], vec.back());
vec.pop_back();

结果是：

vec = {1, 2, 5, 4};

这里，我们将要删除的元素3与最后一个元素5交换了，然后使用pop_back删除了最后一个元素。这样，元素3被删除了，但是元素的顺序改变了。

清空vector：

vec.clear(); // 删除vec中的所有元素

在C++的std::vector中，back()是一个成员函数，它返回对容器中最后一个元素的引用。换言之，back()提供了一种方式来访问向量的最后一个元素，而无需知道其确切索引。如果你有一个std::vector<int>，比如：

std::vector<int> vec = {1, 2, 3, 4, 5};

那么vec.back()将返回5，这是向量中的最后一个元素。

注意，如果向量为空，那么调用back()的行为是未定义的。因此，在调用back()之前，最好先确保向量不为空。

以上是一些基本的std::vector使用方法，std::vector还有很多其他功能，例如排序(std::sort(vec.begin(), vec.end()))、查找(std::find(vec.begin(), vec.end(), value))等。

模拟过程

求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上

由外向内一圈一圈这么画下去。

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

那么我按照左闭右开的原则，来画一圈：

Day 2 数组：977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ

这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。

这也是坚持了每条边左闭右开的原则。

下面代码看出while循环里判断的情况是很多的，代码里处理的原则也是统一的左闭右开。

代码如下：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            // 每转一圈，将（i,j）赋值为这一圈起点位置（startx,starty）
            i = startx; 
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

时间复杂度： $O(\ n^2)$ : 模拟遍历二维矩阵的时间
空间复杂度： $O (1)$