Day2双指针法排序，滑动窗口，螺旋矩阵

By HQWQF 2023/12/14

笔记

977.有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/

返回一个非递减顺序排序的整数数组每个元素的平方后组成的新数组，新数组也按非递减顺序排序。

解法：双指针法

由于给定数组本身是有序的，我们可以将其看作正数和非正数部分，在每个元素平方后，这两个部分内部还是有序的，我们可以使用双指针法对比这两个部分中的元素，然后优先把平方后大的数放入结果数组即可。

双指针法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) 
    {
        int k = nums.size() - 1;
        vector<int> result(nums.size(), 0);
        //两个指针分别指向数组头和尾，相向移动，即先对比两个部分平方后的大数
        for(int i = 0,j = nums.size() - 1;i <= j;)
        {
            //更大的放入到结果数组末尾，因为结果数组需要按非递减顺序排序
            if(nums[i] *nums[i] <= nums[j] *nums[j])
            {
                result[k--] = nums[j] *nums[j];
                j--;
            }else
            {
                result[k--] = nums[i] *nums[i];
                i++;
            }            
        }
        return result;
    }
};

双指针法的时间复杂度是O(n)，相比遍历平方后排序的暴力解法的O(n + nlog n)好一些。

注释：

这题使用双指针法是比较容易想到的，但是正向思维是让指针从数组中间最接近0的位置开始向两边移动（因为这样就可以从小开始排序），而这样指针移动的终止条件会比较复杂，且数组全正全负的情况需要另外处理。
而如果使用逆向思维，指针从两端开始相向移动，终止条件和特殊情况的处理会比较简单，我们只需要从结果数组的尾部放入元素就可以达到非递减顺序排序的目的了。

209.长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

数组中满足其总和大于等于特定值的长度最小的 连续子数组的长度。如果不存在符合条件的子数组，返回 0。

解法：滑动窗口

使用两个指针，分别代表窗口的两端，这个窗口就代表连续子数组，为了得到最短的窗口，窗口右端一步步向右滑动，每次滑动后都会尝试滑动左端点来让窗口尽可能短，并尝试更新窗口最短值。窗口右端滑动到末尾即代表得出了窗口最短值。

滑动窗口法

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) 
    {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口左端点
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) 
        {
            sum += nums[j];
            //使用while 循环将滑动窗口左端点滑到合适的位置
            while (sum >= s) {
                subLength = (j - i + 1); 
                result = result < subLength ? result : subLength;//尝试更新最小值
                sum -= nums[i++]; 
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

注释：

在根据数据获取某种最小值（最大值）的题目中，往往会将result 变量设置为数值上的最小值（最大值），然后在某种遍历中尝试更新result 变量，这样在遍历完成后就获得了最小值（最大值）。
对于result 变量没有更新过的情况往往代表着此数据无法获取这个最值，所以我们就可以通过检测result 变量是否还是数值上的最小值（最大值）来判断这种特殊情况。
for循环比while循环好的一个地方是，for循环有清晰的退出条件，能用for循环尽量用for循环。

59.螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

解法：模拟过程

本题不包含任何算法知识，关键是看出螺旋填充一个矩阵的过程可以分解为填充数个环，填充一个环的过程可以分为4段，考验我们将一个复杂过程分解为更小的规律性过程，然后在代码中需要注意的是循环的边界，以及填充过程中下标的变化。

class Solution {
public:
vector<vector<int>> generateMatrix(int n)
{
    int nob = 1;
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    int ring = n / 2;//环数，n为奇数的话会留下最中间的元素不填充

    int col = n;
    for (int offset = 0; offset < ring; offset++)
    {
        //环中的相对下标
        int ringx = 0;
        int ringy = 0;
        for (int i = 0; i < col - 1; i++)
        {
            matrix[offset + ringy][offset + ringx] = nob;
            nob++;
            ringx++;
        }
        for (int i = 0; i < col - 1; i++)
        {
            matrix[offset + ringy][offset + ringx] = nob;
            nob++;
            ringy++;
        }
        for (int i = col - 1; i > 0; i--)
        {
            matrix[offset + ringy][offset + ringx] = nob;
            nob++;
            ringx--;
        }
        for (int i = col - 1; i > 0; i--)
        {
            matrix[offset + ringy][offset + ringx] = nob;
            nob++;
            ringy--;
        }
        col -= 2;//下一个环的边长
    }
    //n为奇数的话填充最中间的元素
    if (n % 2 != 0)
    {
        matrix[n / 2][n / 2] = n * n;
    }
    return matrix;
}
};