NO.2 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II

题目链接：977.有序数组的平方

• 前置条件：数组是非递减的，如果是乱序的数组应该就只能暴力解法
• 暴力解法：直接遍历，对每个元素都进行平方，然后对平方后的结果进行排序。但这样就没有使用上非递减这个条件

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i)
        {
            nums[i] = nums[i] * nums[i];
        }

        std::sort(nums.begin(), nums.end());

        return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 双指针法：平方后数据的大小顺序与求绝对值的顺序一样，大的在头尾，中间的是小数。因此可以头尾各一个指针，对比绝对值大小，然后排序，时间复杂度O(n)

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res;
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right)
        {
            if(abs(nums[left]) < abs(nums[right]))
            {
                res.push_back(nums[right] * nums[right]);
                right -= 1;
            }
            else if(abs(nums[left]) > abs(nums[right]))
            {
                res.push_back(nums[left] * nums[left]);
                left += 1;
            }
            else
            {
                if(left == right)
                {
                    // [-4,-1,0,3,10] left == right == 2,指向同一个位置的情况
                    res.push_back(nums[left] * nums[left]);
                    break;
                }
                else
                {
                    // [-7,-3,2,3,11] -3和3的平方相等的情况
                    res.push_back(nums[left] * nums[left]);
                    res.push_back(nums[right] * nums[right]);
                    left += 1;
                    right -= 1;
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
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

题目链接：977. 有序数组的平方
解题思路：我认为实际上是对暴力解法的优化，暴力解法使用两层for循环，该解法把第二层for循环改成了while，只有在必要的时候更新滑动窗口的起始位置
参考链接：https://www.bilibili.com/video/BV1tZ4y1q7XE/?vd_source=8b0f76da42173279a0e6f135870b47a0

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = nums.size() + 1;
        int sum = 0;
        int begin = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            // 使用while是考虑[1, 1, 1, 1, 100], target=100的情况
            while(sum >= target)
            {
                // 更新最小长度
                res = min(res, i - begin + 1);
                sum -= nums[begin];
                begin += 1;
            }
        }
        return (res == nums.size() + 1) ? 0 : res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题目链接：59. 螺旋矩阵 II
解题思路：该题没有什么技巧，按照题意写代码即可，注意矩阵的边界不要乱。还有就是当n为奇数时，中间的一个元素要单独赋值。
参考讲解链接：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html#%E6%80%9D%E8%B7%AF

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<int> vec(n, 0);
        vector<vector<int>> res(n, vec);
        int left = 0;
        int right = n-1;
        int top = 0;
        int down = n-1;
        int index = 0;
        while(left <= right)
        {
            for(int x = left; x < right; ++x)
            {
                index += 1;
                res[top][x] = index;
            }
            for(int y = top; y < down; ++y)
            {
                index += 1;
                res[y][right] = index;
            }
            for(int x_ = right; x_ > left; --x_)
            {
                index += 1;
                res[down][x_] = index;
            }
            for(int y_ = down; y_ > top;--y_)
            {
                index += 1;
                res[y_][left] = index;
            }

            // 中间元素
            if(left == right)
            {
                index += 1;
                res[left][top] = index;
            }

            // 缩圈
            left += 1;
            right -= 1;
            top += 1;
            down -= 1;
        }
        return res;
    }
};
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
42
43
44
45
46
47
48
49