學習鏈接

題目鏈接：

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

https://leetcode.cn/problems/minimum-size-subarray-sum/

https://leetcode.cn/problems/spiral-matrix-ii/

文章鏈接：

https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

視頻鏈接：

https://www.bilibili.com/video/BV1QB4y1D7ep

https://www.bilibili.com/video/BV1tZ4y1q7XE

https://www.bilibili.com/video/BV1SL4y1N7mV/

第一想法

有序數組的平方

題目給出一個非遞減的整數型數組（可能包含負數），需要返回一個非遞減且原數組經過平方之后的新數組。要求時間復雜度為O(n）。

初步想法：將數組中每個值平方得到一個新的數組，之后對數組進行排序。

思考二：由于沒有內存的限制，可以利用一個輔助數組。先對原數組中每個元素平方，同時將其排序后插入到新數組。

思考三：先對原數組中的值取絕對值，進行一個非遞減排序后，再挨個平方組成新的數組。

長度最小的子數組

這個問題一看就有點難。

思路一：暴力求解，相當于雙指針求解。直接兩層for循環，遍歷的找。第一層for循環決定起點，第二層for循環看加到第幾個數。如果加起來超過了目標值，則退出。如果沒超過目標值，就往后移。等于目標值的時候，記錄長度。用一個變量來記錄最小長度。

思路二：首先一個一個的看，是否有對應的目標值。之后兩個塊一起看，是否有滿足的序列，有則返回序列長度，沒有則三個快一起看。兩個快可以用i 和i+1 ,這樣來表示。不知道這是不是滑動窗口。

螺旋矩陣II

看完代碼隨想錄之后的想法

有序數組的平方

題目：給你一個按?非遞減順序?排序的整數數組?nums，返回?每個數字的平方?組成的新數組，要求也按?非遞減順序?排序。

最初實現：

部分結果正確，但是提交會出現超時問題。排序算法可以優化一下

class Solution { public:vector<int> sortedSquares(vector<int>& nums) {int length = nums.size();int middle;for(int i = 0; i < length; i++){nums[i] = nums[i] * nums[i]; }for(int j = 0; j < length; j++){for(int k = 0; k < length-1; k++){if(nums[k] > nums[k + 1]){middle = nums[k];nums[k] = nums[k + 1];nums[k + 1] = middle;}}}return nums;} };#優化后的代碼： #（1）暴力破解法 時間復雜度是 O(n + nlogn) class Solution { public:vector<int> sortedSquares(vector<int>& nums) {for(int i = 0; i < nums.size(); i++){nums[i] *= nums[i];}sort(nums.begin(),nums.end()); //快速排序return nums;} };

利用雙指針法，兩個指針i和j，分別指向起始和結束位置，依次從數組兩端挑選最大的數。放到一個新的數組中，新數組的指針指向終止位置，以此從后往前填充。斯巴拉西。

雙指針法真好用。

#依照雙指針思路寫的代碼 時間復雜度為O(n) class Solution { public:vector<int> sortedSquares(vector<int>& nums) {int length = nums.size()-1;int j = length;int i = 0;vector<int> result(nums.size(), 0);while(i <= j){int double_i = nums[i] * nums[i];int double_j = nums[j] * nums[j];if(double_i > double_j){result[length--] = double_i;i++;}else{result[length--] = double_j;j--;}}return result;} };

需要注意的點包括：雙指針思路，vector 變量定義。（C++ 還是不熟，得加快學習速度）。

長度最小的子數組

題目：

給定一個含有?n?****個正整數的數組和一個正整數?target?。

找出該數組中滿足其和?****≥ target?**的長度最小的?連續子數組?[numsl, numsl+1, ..., numsr-1, numsr]?，并返回其長度。**如果不存在符合條件的子數組，返回?0?。

自己思路：

1）暴力解法—先兩個兩個加起來看超不超過，兩個沒有超過的，那就三個連續的加起來。可能會有多個符合的，但是只需要返回長度，所以找到一個就行。有從小到大長度去試和從大到小去試兩種思路。

2）暴力解法2：用兩個變量指示窗口，i，j。然后兩層for循環。

初始代碼：

顯示超過了時間限制，也不知道有沒有bug。（有的，當不滿足，返回0）

class Solution { public:int minSubArrayLen(int target, vector<int>& nums) {int length = nums.size() - 1;int min = 1;int sum = 0;while(sum < target){for(int i = 0; i <= length; i++){int sum = 0;for(i = 0; i < min; i++){sum += nums[i];}if(sum >= target){break;}else{min++;}}}return min;} };#兩層for循環，暴力解法 class Solution { public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX; // 最終的結果int sum = 0; // 子序列的數值之和int subLength = 0; // 子序列的長度for (int i = 0; i < nums.size(); i++) { // 設置子序列起點為isum = 0;for (int j = i; j < nums.size(); j++) { // 設置子序列終止位置為jsum += nums[j];if (sum >= s) { // 一旦發現子序列和超過了s，更新resultsubLength = j - i + 1; // 取子序列的長度result = result < subLength ? result : subLength;break; // 因為我們是找符合條件最短的子序列，所以一旦符合條件就break}}}// 如果result沒有被賦值的話，就返回0，說明沒有符合條件的子序列return result == INT32_MAX ? 0 : result;} };

滑動窗口：不斷調節子序列的起始位置和終止位置，從而得出我們想要的結果。

只用一個for循環，應該表示的是遍歷的終止位置。

我之前自己思考從大往小去找的思路跟這個很像。

窗口就是 滿足其和 ≥ s 的長度最小的 連續 子數組。

窗口的起始位置如何移動：如果當前窗口的值大于s了，窗口就要向前移動了（也就是該縮小了）。

窗口的結束位置如何移動：窗口的結束位置就是遍歷數組的指針，也就是for循環里的索引。

牛逼！

class Solution { public:int minSubArrayLen(int target, 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，每次更新 i（起始位置），并不斷比較子序列是否符合條件while(sum >= target){sublength = (j - i + 1); // 取子序列的長度result = result > sublength? sublength : result;sum -= nums[i++]; // 這里體現出滑動窗口的精髓之處，不斷變更i（子序列的起始位置）}} // 如果result沒有被賦值的話，就返回0，說明沒有符合條件的子序列return result == INT32_MAX? 0 : result;} };

• 時間復雜度：O(n)
• 空間復雜度：O(1)

時間復雜度主要是看每一個元素被操作的次數，每個元素在滑動窗后進來操作一次，出去操作一次，每個元素都是被操作兩次，所以時間復雜度是 2 × n 也就是O(n)。

螺旋矩陣II

給你一個正整數?n?，生成一個包含?1?到?n2?所有元素，且元素按順時針順序螺旋排列的?n x n?正方形矩陣?matrix?。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-qstntN6u-1685171525400)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/1cb7305b-78a9-40f9-91bf-e052b105fa22/Untitled.png)]

自己思路：首先，生成1-n平方的所有元素，不難。關于排序，最初想法是找規律。但是針對奇偶數，不同排的情況各不一樣，應該不能這樣做。想了十分鐘，沒有思路，直接看解析。

代碼隨想錄思路：本題并不涉及到什么算法，就是模擬過程，但卻十分考察對代碼的掌控能力。一定要堅持循環不變量原則。

模擬順時針畫矩陣的過程:

• 填充上行從左到右
• 填充右列從上到下
• 填充下行從右到左
• 填充左列從下到上

由外向內一圈一圈這么畫下去。

class Solution { public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n,0)); // 使用vector定義一個二維數組int startx = 0, starty = 0; // 定義每循環一個圈的起始位置int loop = n / 2; // 每個圈循環幾次，例如n為奇數3，那么loop = 1 只是循環一圈，矩陣中間的值需要單獨處理int mid = n / 2; // 矩陣中間的位置，例如：n為3， 中間的位置就是(1，1)，n為5，中間位置為(2, 2)int count = 1; // 用來給矩陣中每一個空格賦值int offset = 1; // 需要控制每一條邊遍歷的長度，每次循環右邊界收縮一位int i, j;while(loop--){i = startx;j = starty;// 下面開始的四個for就是模擬轉了一圈// 模擬填充上行從左到右(左閉右開)for(j = starty; j < n -offset; j++){res[startx][j] = count++;}// 模擬填充右列從上到下(左閉右開)for(i = startx; i < n - offset; i++){res[i][j] = count++;}// 模擬填充下行從右到左(左閉右開)for(; j > starty; j--){res[i][j] = count++;}// 模擬填充左列從下到上(左閉右開)for(; i > startx; i--){res[i][j] = count++;} // 第二圈開始的時候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)startx++;starty++;offset += 1; // offset 控制每一圈里每一條邊遍歷的長度}// 如果n為奇數的話，需要單獨給矩陣最中間的位置賦值if (n % 2 ){res[mid][mid] = count;}return res;}};

• 時間復雜度 O(n^2): 模擬遍歷二維矩陣的時間
• 空間復雜度 O(1)

這種模擬題得找到它的規律去做，我剛開始想得找每一行的規律，但這樣太復雜了。還要各種判斷，題目給出了順時針賦值，但是有很多圈。要想辦法找到能夠重復的模板，比如如何賦值一圈。

今日收獲

1、sort函數的排序方法類似于快排方法僅適用于普通數組和部分類型的容器，時間復雜度為n*log2(n)

sort(起始地址，結束地址，比較器); 其中比較器可以省略，默認升序

**對vector排序：**sort(vec.begin(),vec.end()）

其中vec.begin()返回的是一個迭代器，該迭代器指向vec的起始元素。

2、滑動窗口

3、模擬題

總結

以上是生活随笔為你收集整理的day 2 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。