目录

977.有序数组的平方

209.长度最小的子数组

59.螺旋矩阵||

数组总结导图

---

977.有序数组的平方

力扣题目链接

第一想法：非递减（有重复，返回多值），新数组是原元素平方，时间复杂度O(n)，可以原地修改（双指针（事实上这里以为可以用双指针的思路有误，见下解决办法）），在此之上需重排顺序

难点：发现不知道怎么设置指针，以及如何用指针来进行排序操作。试图改为暴力法，只想起来了冒泡排序（两个for循环，每一轮，注意多减一个1）的实现方式，而且还不熟练，时间复杂度O(n^2)

状态：暴力，超时

解决办法：

1.暴力优化：直接用sort，时间复杂度O(n+nlogn)

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for (int i = 0; i < A.size(); i++) {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); // 快速排序O(nlogn)
        return A;
    }
};

2.双指针法：（之前没有从题目出发，想当然的直接以为双指针，没抓住数组本身是个非递减数组，平方后由于负数的存在，此时平方的最大值便出现在了两端，又由于新数组要非递减，那么此时就可以通过双指针，从两边先找最大，逐渐找最小。新声明一个vector倒序赋值新元素。）

（那么感觉双指针，在原地修改，以及两头各做一件事，以及能找到两个指针一个找元素一个找下标，这种场景中可以考虑一下使用）(目前的思路，待完善）

时间复杂度：O(n)

空间复杂度：O(n)

// 双指针
        vector<int> result(nums.size(), 0); // 需要新声明一个数组来存储平方后的值，不是原地修改，否则元素又要被计算又要被更新。新声明一个和输入向量大小相同，且每个元素初始化为0的新向量result
        int k = nums.size() - 1; // 倒序更新索引
        for(int i = 0, j = nums.size() - 1; i <= j;) { // i++,j--是有条件的
            if (nums[i] * nums[i] < nums[j] * nums[j]) {
                result[k--] = nums[j] * nums[j];
                j--; //j减操作不能写在上面这一步，否则会出现算了nums[j]后，又减1，然后计算nums[j-1]，再将两者相乘的情况
                
            } else { // i和j平方相等时，存i的平方和存j的平方都一样
                result[k--] = nums[i] * nums[i];
                i++;
                
            }
        }
        return result;

209.长度最小的子数组

力扣题目链接

第一想法：暴力解法，两个for循环，一个控制起始，一个控制终止

难点：如何保证长度最小（多个符合总和这一条件的连续数组），卡在了只晓得给result赋值0致使不知道怎么保证新得到的sublength会比他更小

状态：没实现，不知道怎么实现在比较中得出最小的长度，

解决方法：

1.暴力

可给变量初始化大值来进行判别是否有比他更小的，? ：三元运算符的使用，break结束循环

时间复杂度O(n^2)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX; // 除了赋值0，还可以赋值大值，以实现判断是否有比他更小的
        int sum = 0;
        int subLength = 0; // 子串长度
        for (int i = 0; i < nums.size(); i++) {
            sum = 0; // sum在每一轮要重新更新为0
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];
                if (sum >= target) {
                    subLength = j - i + 1; //利用j，得出子串长度
                    result = result < subLength ? result : subLength; // 学会利用?:
                    break; // 找到后，结束当前循环
                }
            }
        }
        return result == INT32_MAX ? 0 : result; // 如果result没有被赋值，即没有符合条件的子列，返回0
    }
};

2.滑动窗口  (类似双指针，只不过是取的两个指针之间的一个区间）（分清谁记录，谁遍历）

（窗口内是什么，起始位置和结束位置分别如何移动）

（移动起始位置后，窗口内的值也要相应更改）

（仅使用的一个for循环里的j是终止位置）

（起始位置的移动，当窗口的值大于target了，窗口就要向前移动了，起始位置移动来缩小窗口）（结束位置就是遍历这个数组）（窗口内就是满足其和>=target的最小长度子串）

时间复杂度O(n)：for循环里嵌套while循环不是就直接是O(n^2)了，主要还是看每一个元素被操作的次数，滑动窗口后进来和出去分别操作一次，即共操作两次，时间复杂度2*n,即O(n)

空间复杂度O(1)

        // 滑动窗口
        int i = 0; // 窗口起始位置
        int sum = 0;  // 窗口数值之和
        int result = INT32_MAX;
        int subLength = 0; // 窗口长度
        for (int j = 0; j < nums.size(); j++) { // j是终止位置（如果是起始位置，那么找终止位置又要一个一个遍历后面，岂不又变成暴力解法了）
            sum += nums[j];
            // 如何向前移动起始位置精髓
            while (sum >= target) { // 使用while,以不断比较，一旦找到一个符合的子序列了，定住终止位置，向前移动起始位置，即找到当前j下最小的子串长度
                subLength = j - i + 1;
                result = min(result, subLength);
                sum -= nums[i++]; // 滑动窗口关键，变更子序列大小，通过更改起始位置,sum也相应改变
            }
        }
        return result == INT32_MAX ? 0 : result;

59.螺旋矩阵||

第一想法：n维，i不动，j++走到一行末尾，然后j不动，i--走到右下角，再然后往左走，j--，然后往上走i--

难点：这样思路需要多个for循环，且不知怎样终止，毕竟螺旋一直往内螺，直到最后边长为1

状态：未实现

解决办法：while循环外有公共的变量starx,stary，也用到循环不变量原则，这里的不变量就是让遍历每一条边时规则一致，方便一圈一圈的循环，比如这里区间左闭右开，那么在遍历每一条边时，就是第一个点加上这条边。            前面的思路主要是没有想到用公共变量和while循环来囊括，以及没有意识到边界处理，及循环不变量。同时把for循环给孤立了，事实上每个for循环有联系，比如上一个for循环结束后，此时变量i或j便等于某值了，那么下一个循环便可直接用。    而且还要注意奇数圈与偶数圈的不同处理。

 vector<vector<int> > newOne(r, vector<int>(c, 0));定义r*c二维vector

时间复杂度O(n^2)模拟遍历二维矩阵的时间（每个元素都被访问一次，共访问n^2次，对于每个元素，又是进行的O(1）操作，所以，总体来说，时间复杂度为n^2)

空间复杂度O(1)题目本身就是二维的，不是我算法额外开辟的，所以复杂度1

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> a(n, vector<int>(n, 0)); //定义二维数组
        int starx = 0, stary = 0; // 定义每一圈起始循环位置
        int count =  1; // 给每一个空格赋值
        int con = 1; // 控制每一条边遍历长度，每循环一次边界减小1
        int loop = n / 2; // 控制循环的圈数，奇数n=5则是两圈，最中间那个空格单独处理
        int mid = n / 2; // 矩阵中间位置。主要用于n为奇数时

        while (loop--) { //圈数走完，循环结束，奇数中间格另做处理
            int i = starx;
            int j = stary; // 让每个for循环联系起来，公共变量
            // 左闭右开
            // 往右走
            for (; j < n - con; j++) {
                a[starx][j] = count++; // j在等于该边最后一个空格位置，即j=n-con时退出该循环，并用于下一个循环
            }
            // 往下走
            for (; i < n - con; i++) {
                a[i][j] = count++;
            }
            // 往左走
            for (; j > stary; j--) {
                a[i][j] = count++;
            }
            // 往上走
            for (; i > starx; i--) {
                a[i][j] = count++;
            }

            starx++;
            stary++; // 每圈起始位置+1

            con++; // 边界控制，缩1
        }
        if (n % 2) { // n为奇数，单独给矩阵最中间赋值
            a[mid][mid] = count;
        }
        return a;
    }
};

数组总结导图

碎碎念：赶进度2。。（相当于实际上原本一天的量用了两天来完成。。。再接再厉！）博客内容还可以继续精简，精准抓住难点和解决办法，先完整过一遍，注意效率，定量且连续，加油。