代码随想录：滑动窗口和螺旋矩阵

滑动窗口

209. 长度最小的子数组

• 题目lc209
• 暴力：双重循环，对每个起始位置都记录一个长度，最后输出最小长度
• 滑动窗口（类似双指针）：解决三个问题
  1. 窗口里是什么：子数组的sum
  2. 窗口起始位置：窗口的第一个值
  3. 窗口结束位置：窗口的最后一个值
• 代码如下：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ret = 1e9 + 10;
        int sum = 0;
        int n = nums.size();
        for(int i = 0, j = 0; j < n; j++){
            sum += nums[j];
            while(sum >= target){
                ret = ret < j - i + 1 ? ret : j - i + 1;
                sum -= nums[i++];
            }
        }
        return ret == 1e9 + 10 ? 0 : ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

lc904

• 题目lc904
• 代码如下：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int>mp;
        int ret = 0;
        int n = fruits.size();
        for(int i = 0, j = 0; j < n; j++){
            ++mp[fruits[j]];
            while(mp.size() > 2){
                --mp[fruits[i]];
                if(mp[fruits[i]] == 0){
                    mp.erase(fruits[i]);  // 这里erase会再先找一次迭代器位置，所以可以先find
                }
                ++i;
            }
            ret = max(ret, j - i + 1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

螺旋矩阵

lc59

• 题目lc59
• 模拟原则：四条边都遵守左闭右开原则
• 代码如下：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>>ret(n, vector<int>(n));  // 定义数组
        // 定义四条边的边界
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int element = 1, last = n * n;
        while(element <= last){
            // 上
            for(int i = left; i <= right; i++){
                ret[top][i] = element++;
            }
            top++;
            // 右边
            for(int i = top; i <= bottom; i++){
                ret[i][right] = element++;
            }
            right--;
            // 下边
            for(int i = right; i >= left; i--){
                ret[bottom][i] = element++;
            }
            bottom--;
            // 左边
            for(int i = bottom; i >= top; i--){
                ret[i][left] = element++;
            }
            left++;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

lc54

• 题目lc54
• 代码如下：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int row = matrix.size(), column = matrix[0].size();
        int last = row * column, element = 1; // element记录是否遍历全部元素
        int top = 0, left = 0, right = column - 1, bottom = row - 1;
        while(element <= last){
            // 上
            for(int i = left; i <= right; i++, element++){
                ret.push_back(matrix[top][i]);
            }
            top++;
            if(element > last){
                break;
            }
            // 右边
            for(int i = top; i <= bottom; i++, element++){
                ret.push_back(matrix[i][right]);
            }
            right--;
            if(element > last){
                break;
            }
            // 下边
            for(int i = right; i >= left; i--, element++){
                ret.push_back(matrix[bottom][i]);
            }
            bottom--;
            if(element > last){
                break;
            }
            // 左边
            for(int i = bottom; i >= top; i--, element++){
                ret.push_back(matrix[i][left]);
            }
            left++;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41