代码随想录算法训练营第二天 |977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II ，总结

代码随想录算法训练营第二天 |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

思路：看到这个题目的要求，由于初始数组是一个从小到大的数组，但是每个数平方之后都是一个正数，大小排列顺序需要重新排列，就可以用双指针分别从两头开始，相向而行，比较大小从而排列成新的数组。每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。

class Solution {public:
    vector sortedSquares(vector& nums) { int n = nums.size();
        vector ans(n);
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) { if (nums[i] * nums[i] > nums[j] * nums[j]) { ans[pos] = nums[i] * nums[i];
                ++i;
            }
            else { ans[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums的长度。

空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。

• 暴力解法也非常简单，将数组中的数据乘方并排序。

  class Solution {public:
      vector sortedSquares(vector& nums) { vector ans;
          for (int num: nums) { ans.push_back(num * num);
          }
          sort(ans.begin(), ans.end());
          return ans;
      }
  };
  

  复杂度分析

  时间复杂度：O(nlog⁡n)，其中 n 是数组 nums 的长度。

  空间复杂度：O(log⁡n)。除了存储答案的数组以外，我们需要 O(log⁡n)的栈空间进行排序。

  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

  思路：使用滑动窗口的办法，定义两个指针 start和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，用sum代表由开始到结束的子数组的和。

  class Solution {public:
      int minSubArrayLen(int s, vector& nums) { int n = nums.size();
          if (n == 0) { return 0;
          }
          int ans = INT_MAX;
          int start = 0, end = 0;
          int sum = 0;
          while (end < n) { sum += nums[end];
              while (sum >= s) { ans = min(ans, end - start + 1);
                  sum -= nums[start];
                  start++;
              }
              end++;
          }
          return ans == INT_MAX ? 0 : ans;
      }
  };
  

  复杂度分析

  时间复杂度：O(n)，其中 n 是数组的长度。指针 start和 end最多各移动 n 次。

  空间复杂度：O(1)。

  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/

  思路：主要需要想好如何模拟矩阵生成的过程，有了清晰的模拟思路就可以很好地去实现代码。按照要求，初始位置设为矩阵的左上角，初始方向设为向右。若下一步的位置超出矩阵边界，或者是之前访问过的位置，则顺时针旋转，进入下一个方向。如此反复直至填入 n2个元素。

  class Solution {public:
      vector> generateMatrix(int n) { int maxNum = n * n;
          int curNum = 1;
          vector> matrix(n, vector(n));
          int row = 0, column = 0;
          vector> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // 右下左上
          int directionIndex = 0;
          while (curNum <= maxNum) { matrix[row][column] = curNum;
              curNum++;
              int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
              if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) { directionIndex = (directionIndex + 1) % 4;  // 顺时针旋转至下一个方向
              }
              row = row + directions[directionIndex][0];
              column = column + directions[directionIndex][1];
          }
          return matrix;
      }
  };
  

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

  空间复杂度 O(1)。

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

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

  今天的题目任务难度与数量都比第一天的多，新加了不少困难，但是也收获多多。对数组的处理主要就是对于数组下标位置的理解，去处理该处理位置的数据。