文章目錄

前言

一、二分查找法（LeetCode--704）

二、移除元素（LeetCode--27）

三、有序數組的平方（LeetCode--977）

四、長度最小的子數組（LeetCode--209）

五、螺旋矩陣II（LeetCode--59）

---

前言

跟隨代碼隨想錄，學習數組相關的算法題目，記錄學習過程中的tips。

---

一、二分查找法（LeetCode--704）

【1】算法功能：在有序數組中，查找指定元素，時間復雜度為O(log N)。

【2】算法思想：定義首尾指針分別指向數組的首尾元素，若中間元素的值小于目標值則將首指針移動至中間元素右側，若中間元素的值大于目標值則將尾指針移動至中間元素的左側，若相等則返回下標。

【3】代碼實現：在左閉右閉的區間內查找。

class Solution {
public:int search(vector<int>& nums, int target) {int low = 0, high = nums.size() - 1;while (low <= high) {int mid = (low + high) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {low = mid + 1;} else {high = mid - 1;}}return -1;}
};

【4】易錯點：①注意while循環的判定條件；②注意high的更新條件。

---

二、移除元素（LeetCode--27）

在之前的刷題中已經遇到過，且代碼隨想錄的解法與當時我的初次解法相同，見【LeetCode算法】第27題：移除元素-CSDN博客。

---

三、有序數組的平方（LeetCode--977）

【1】題目描述：

【2】解決思想：首先，找到正負元素的分界線，利用雙指針法來解決。i指針指向最后一個負元素，j指針指向第一個正元素。每次比較i和j元素的大小，誰小就加入目標數組中。i指針向左移動，j指針向右移動。

【3】C++代碼：

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> ret;//最終返回的數組//找到首個>=0的元素(分界線)int k = 0;int len = nums.size();while (k < len && nums[k] < 0) {++k;}//雙指針法：i從k處往左，j從k處往右int i = k - 1, j = k;while (i >= 0 || j < len) {if (i < 0) {ret.push_back(nums[j] * nums[j]);++j;} else if (j >= len) {ret.push_back(nums[i] * nums[i]);--i;} else if (abs(nums[i]) < abs(nums[j])) {ret.push_back(nums[i] * nums[i]);--i;} else {ret.push_back(nums[j] * nums[j]);++j;}}return ret;}
};

【4】時間復雜度：O(N)。

【5】空間復雜度：O(1)，不算目標數組ret。

---

四、長度最小的子數組（LeetCode--209）

【1】題目描述：

【2】解決思想：滑動窗口。定義兩個指針分別指向滑動窗口的起始位置和終止位置。在主循環中，讓終止位置不斷后移，每次后移均加上掃過的元素值。當累加值大于等于目標值時，循環縮小起始位置（為了找到最小的數組長度）。

【3】C++代碼：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int i = 0;//滑動窗口起始位置int sum = 0;int ret = INT_MAX;//j指向滑動窗口的終止位置for (int j = 0; j < nums.size(); ++j) {sum += nums[j];//循環縮小窗口的起始位置while (sum >= target) {ret = min(ret, j - i + 1);sum -= nums[i++];}}return ret == INT_MAX? 0 : ret;}
};

【4】時間復雜度：O(N)。

【5】空間復雜度：O(1)。

【6】啟示：當在一個樣本空間中尋找一組滿足某些條件的連續的子空間時，可以考慮采用滑動窗口方法。

---

五、螺旋矩陣II（LeetCode--59）

【1】題目描述：

【2】解決思想：如下圖所示，每一圈分為四種情況來處理：最上面、最右面、最下面、最左面。同時，每次處理每一條邊的時候都遵循左閉右開原則（處理最左邊節點，不處理最右邊節點），使得每一條邊的處理規則都一致。轉的圈數是n/2，當n為奇數時最后需要額外添加最中間的一個洞。

【3】C++代碼：

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> ret(n, vector<int>(n, 0));int startX = 0, startY = 0;//起始點位置int offset = 1;//每轉一圈，偏移量+1int count = 1;//填入數組中的值int circleNum = n / 2;//轉的圈數for (int k = 0; k < circleNum; ++k) {int i, j;//第一條邊：最上面for (j = startY; j < n - offset; ++j) ret[startX][j] = count++;//第二條邊：最右面for (i = startX; i < n - offset; ++i)ret[i][j] = count++;//第三條邊：最下面for (; j > startY; --j)ret[i][j] = count++;//第四條邊：最左面for (; i > startX; --i)ret[i][j] = count++;startX++;startY++;offset++;}//維度為奇數時，填中間的一格if (n % 2 == 1)ret[startX][startY] = count;return ret;}
};

【4】時間復雜度：O(N^2)

【5】空間復雜度：O(1)，不算存儲數據的數組。

【6】啟示：針對模擬轉圈的場景，找到一致性的處理規則很關鍵。