代码随想录算法训练营第二天 | 滑动窗口 + 螺旋矩阵
文章目录
- Leetcode209 长度最小的连续子数组
- 双指针/滑动窗口
- Leetcode59 螺旋矩阵
- 初始思路：找规律按索引填充
Leetcode209 长度最小的连续子数组
链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
代码随想录: https://programmercarl.com/
时间复杂度: O(logN)
空间复杂度: O(1)
双指针/滑动窗口
利用左右指针依次遍历.
当sum >= target时, 记录当前长度, 并开始右移left指针, 寻找最短的连续子数组
当sum < target时, 右移right指针, 直到找到满足要求的结果
引入标志位finded, 用于记录是否找到过有效结果, 若找不到则返回0
时间复杂度: O(N^2)
空间复杂度: O(1)
int minSubArrayLen(int target, std::vector<int> & nums) {if (nums.empty()) {return 0;}int left = 0, sum = 0, current_length = INT_MAX;bool finded = false;for (int right = 0; right < nums.size();) {sum += nums[right++];while (sum >= target) {current_length = std::min(current_length, right - left);finded = true;sum -= nums[left++];}}return finded ? current_length : 0;
}
Leetcode59 螺旋矩阵
链接:https://leetcode.cn/problems/spiral-matrix-ii
初始思路：找规律按索引填充
- 预先分配结果空间为n * n, 因此空间复杂度为O(N^2)
- 由于会遍历整个二维数组, 因此时间复杂度也是O(N^2)
- 顺时针的填充方向可分为两组: 向右向下, 向左向上
- 每组方向上填充的数量依次为n, n-1, n-2, …, 1. 且方向为交替出现
- 当n和 i 的奇偶性一致时, 填充方向为向右向下. 不一致时填充方向为向左向上.
注意事项:
每组方向填充结束后, 由于下一组一定是先横向填充, 因此需主动更新一次列索引
std::vector<std::vector<int>> generateMatrix(int n) {if (n <= 0) {return {};}if (n == 1) {return { {1} };}// 预先分配内存空间std::vector<std::vector<int>> result;result.resize(n);for (auto & res : result) {res.resize(n);}// 开始填充// 标志位：奇数是否向右向下填充bool odd_fill_to_right = (n % 2) != 0;int number = 1, row_index = 0, column_index = 0;for (int i = n; i > 0; i--) {int row_steps = i;int column_steps = i;bool add_index = (i % 2) != 0 ? odd_fill_to_right : !odd_fil_to_right;while (row_steps > 0 && column_steps > 0) {result[row_index][column_index] = number++;if (column_steps > 1) { // 横向填充column_index = add_index ? column_index + 1 : column_index - 1;column_steps--;} else { // 纵向填充if (--row_steps != 0) {row_index = add_index ? row_index + 1 : row_index - 1;}}}column_index = add_index ? column_index - 1 : column_index + 1;}return result;
}