代碼隨想錄 數組部分，代碼可在本地編譯器運行

數組理論基礎

數組是存放在連續內存空間上的相同類型數據的集合。
數組可以方便的通過下標索引的方式獲取到下標下對應的數據。
需要兩點注意的是

• 數組下標都是從0開始的。
• 數組內存空間的地址是連續的

正是因為數組的在內存空間的地址是連續的，所以我們在刪除或者增添元素的時候，就難免要移動其他元素的地址。

例如刪除下標為3的元素，需要對下標為3的元素后面的所有元素都要做移動操作，如圖所示：

數組的元素是不能刪的，只能覆蓋。
那么二維數組直接上圖，大家應該就知道怎么回事了

那么二維數組在內存的空間地址是連續的么？
C++中二維數組在地址空間上是連續的。

704.二分查找

題目：

. - 力扣（LeetCode）
給定一個 n 個元素**有序的（升序）**整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下標為 4

示例 2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

思路

使用二分法的前提條件：數組為有序數組，同時強調數組中無重復元素。因為一旦有重復元素，使用二分查找法返回的元素下標可能不是唯一的。
寫二分法，區間的定義一般為兩種，左閉右閉即[left, right]，或者左閉右開即[left, right)。

二分法第一種寫法

第一種寫法，我們定義 target 是在一個在左閉右閉的區間里， 也就是[left, right] （這個很重要非常重要）。
區間的定義這就決定了二分法的代碼應該如何寫，因為定義target在[left, right]區間，所以有如下兩點：

• while (left <= right) 要使用 <= ，因為left == right是有意義的，所以使用 <=
• if (nums[middle] > target) right 要賦值為 middle - 1，因為當前這個nums[middle]一定不是target，那么接下來要查找的左區間結束下標位置就是 middle - 1

例如在數組：1,2,3,4,7,9,10中查找元素2，如圖所示：

二分法第二種寫法

如果說定義 target 是在一個在左閉右開的區間里，也就是[left, right) ，那么二分法的邊界處理方式則截然不同。
有如下兩點：

• while (left < right)，這里使用 < ,因為left == right在區間[left, right)是沒有意義的
• if (nums[middle] > target) right 更新為 middle，因為當前nums[middle]不等于target，去左區間繼續尋找，而尋找區間是左閉右開區間，所以right更新為middle，即：下一個查詢區間不會去比較nums[middle]

在數組：1,2,3,4,7,9,10中查找元素2，如圖所示：（注意和方法一的區別）

代碼

• 第一種寫法：

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;class Solution {
public:int search(vector<int>& nums, int target){int left = 0;int right = nums.size() - 1;// 定義target在左閉右閉的區間里，[left, right]while (left <= right)// 當left==right，區間[left, right]依然有效，所以用 <={int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target)// target 在左區間，所以[left, middle - 1]right = middle - 1;else if (nums[middle] < target)// target 在右區間，所以[middle + 1, right]left = middle + 1;elsereturn middle;// 數組中找到目標值，直接返回下標}// 未找到return -1;}
};int main(){vector<int> nums = { -1, 0, 3, 5, 9, 12 }; // 創建一個數組int target = 9;Solution obj;// 創建一個Solution類型的對象obj，int result;//通過obj對象調用search函數，并傳入參數nums、targetresult = obj.search(nums, target);// 輸出結果if (result == -1)cout << "沒有查找到target, 輸出為: " << result << endl;elsecout << "查找到target，輸出為: " << result << endl;return 0;
}

• 時間復雜度：O(log n)

• 空間復雜度：O(1)

• 第二種寫法：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 定義target在左閉右開的區間里，即：[left, right)while (left < right) { // 因為left == right的時候，在[left, right)是無效的空間，所以使用 <int middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle; // target 在左區間，在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右區間，在[middle + 1, right)中} else { // nums[middle] == targetreturn middle; // 數組中找到目標值，直接返回下標}}// 未找到目標值return -1;}
};

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

27.移除元素

題目：

. - 力扣（LeetCode）
給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并返回移除后數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間并原地修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度后面的元素。
示例 1:

輸入： nums = [3,2,2,3], val = 3,
輸出：2, nums = [2,2]
解釋：函數應該返回新的長度 2, 并且nums 中的前兩個元素均為 2。 你不需要考慮數組中超出新長度后面的元素。

示例 2:

輸入： nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,3,0,4]
函數應該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。

你不需要考慮數組中超出新長度后面的元素。

思路-雙指針法

雙指針法（快慢指針法）：** 通過一個快指針和慢指針在一個for循環下完成兩個for循環的工作。**
定義快慢指針

• 快指針：尋找新數組的元素 ，新數組就是不含有目標元素的數組
• 慢指針：指向更新 新數組下標的位置

刪除過程如下：

代碼

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0; // 慢指針for (int fastIndex = 0;fastIndex < nums.size();fastIndex++) {// 不相等時，將原數組(fastIndex數組)中的元素放入新數組(slowIndex代表的數組)中,// 同時slowIndex移到下一個位置if (val != nums[fastIndex]) { nums[slowIndex++] = nums[fastIndex];}}return slowIndex; }
};int main() {vector<int> nums = {0,1,2,3,3,0,4,2}; // 創建一個數組int val = 2;Solution obj;// 創建一個Solution類型的對象obj，int result; //通過obj對象調用removeElement函數，并傳入參數nums、valresult = obj.removeElement(nums,val);// 輸出結果cout << "刪除元素后的數組新長度為： " << result << endl;cout << "刪除元素后的數組為：";for (int i = 0; i < result; i++) {cout << nums[i] << " ";}cout << endl;return 0;
}

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

977.有序數組的平方

題目

. - 力扣（LeetCode）
給你一個按 非遞減順序 排序的整數數組 nums，返回 每個數字的平方 組成的新數組，要求也按 非遞減順序 排序。
示例 1：

輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數組變為 [16,1,0,9,100]，排序后，數組變為 [0,1,9,16,100]

示例 2：

輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]

思路-雙指針

數組其實是有序的， 只不過負數平方之后可能成為最大數了。
那么數組平方的最大值就在數組的兩端，不是最左邊就是最右邊，不可能是中間。
此時可以考慮雙指針法了，i 指向起始位置，j 指向終止位置。
定義一個新數組result，和A數組一樣的大小，讓 k 指向result數組終止位置。
如果A[i] * A[i] < A[j] * A[j] 那么result[k–] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] 那么result[k–] = A[i] * A[i]; 。
如動畫所示：

代碼

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;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[i] * nums[i];i++;}else {result[k--] = nums[j] * nums[j];j--;}}return result;}
};void PrintVector(vector<int>& nums) {for (int i = 0; i < nums.size();i++) {cout << nums[i] << " ";}cout << endl;
}int main() {vector<int> nums = { -4,-1,0,3,10 }; // 創建一個數組Solution obj;// 創建一個Solution類型的對象obj，vector<int> result;//通過obj對象調用sortedSquares函數，并傳入參數numsresult = obj.sortedSquares(nums);// 輸出結果cout << "平方排序后的數組為： " << endl;PrintVector(result);return 0;
}

時間復雜度為O(n)；

209.長度最小的子數組

題目：

. - 力扣（LeetCode）
給定一個含有 n 個正整數的數組和一個正整數 target ，找出該數組中滿足其和 ≥target 的長度最小的 連續 子數組，并返回其長度。如果不存在符合條件的子數組，返回 0。
示例：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的子數組。

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

思路 – 滑動窗口

接下來就開始介紹數組操作中另一個重要的方法：滑動窗口。
所謂滑動窗口，就是不斷的調節子序列的起始位置和終止位置，從而得出我們要想的結果。
在暴力解法中，是一個for循環滑動窗口的起始位置，一個for循環為滑動窗口的終止位置，用兩個for循環 完成了一個不斷搜索區間的過程。
那么滑動窗口如何用一個for循環來完成這個操作呢。
首先要思考 如果用一個for循環，那么應該表示 滑動窗口的起始位置，還是終止位置。
如果只用一個for循環來表示 滑動窗口的起始位置，那么如何遍歷剩下的終止位置？
此時難免再次陷入 暴力解法的怪圈。
所以 只用一個for循環，那么這個循環的索引，一定是表示 滑動窗口的終止位置。
那么問題來了， 滑動窗口的起始位置如何移動呢？
這里還是以題目中的示例來舉例，s=7， 數組是 2，3，1，2，4，3，來看一下查找的過程：

最后找到 4，3 是最短距離。
其實從動畫中可以發現滑動窗口也可以理解為雙指針法的一種！只不過這種解法更像是一個窗口的移動，所以叫做滑動窗口更適合一些。
在本題中實現滑動窗口，主要確定如下三點：

• 窗口內是什么？
  • 窗口就是 滿足其和 ≥ s 的長度最小的 連續 子數組。
• 如何移動窗口的起始位置？
  • 窗口的起始位置如何移動：如果當前窗口的值大于等于s了，窗口就要向前移動了（也就是該縮小了）。
• 如何移動窗口的結束位置？
  • 窗口的結束位置如何移動：窗口的結束位置就是遍歷數組的指針，也就是for循環里的索引。

解題的關鍵在于 窗口的起始位置如何移動，如圖所示：

可以發現滑動窗口的精妙之處在于根據當前子序列和大小的情況，不斷調節子序列的起始位置。

代碼：

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;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 (sum >= target) {subLength = j - i + 1; // 計算子數組的長度result = result < subLength ? result : subLength;sum -= nums[i++];// 移動起始位置}}return result == INT32_MAX ? 0 : result;}
};int main() {vector<int> nums = { 2,3,1,2,4,3 }; // 創建一個數組int target = 7;Solution obj;// 創建一個Solution類型的對象obj，int result;//通過obj對象調用minSubArrayLen函數，并傳入參數target,numsresult = obj.minSubArrayLen(target,nums);// 輸出結果cout << "子數組的長度為： " << result << endl;
}

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

一些錄友會疑惑為什么時間復雜度是O(n)。
不要以為for里放一個while就以為是O(n^2)啊， 主要是看每一個元素被操作的次數，每個元素在滑動窗后進來操作一次，出去操作一次，每個元素都是被操作兩次，所以時間復雜度是 2 × n 也就是O(n)。

59.螺旋矩陣Ⅱ

. - 力扣（LeetCode）

題目

給定一個正整數 n，生成一個包含 1 到 n^2 所有元素，且元素按順時針順序螺旋排列的n* n正方形矩陣。
示例:

輸入: 3
輸出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路

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

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

由外向內一圈一圈這么畫下去。
這里一圈下來，我們要畫每四條邊，這四條邊怎么畫，每畫一條邊都要堅持一致的左閉右開，或者左開右閉的原則，這樣這一圈才能按照統一的規則畫下來。
那么我按照左閉右開的原則，來畫一圈，大家看一下：

這里每一種顏色，代表一條邊，我們遍歷的長度，可以看出每一個拐角處的處理規則，拐角處讓給新的一條邊來繼續畫。
這也是堅持了每條邊左閉右開的原則。

代碼

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;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 offset = 1; // 需要控制每一條邊遍歷的長度，每次循環右邊界收縮一位int count = 1;// 用來給矩陣中每一個空格賦值int i, j;while(loop--){i = startx;j = starty;for (j; j < n - offset; j++) { // 填充上行從左到右(左閉右開)res[i][j] = count++;}for (i; 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 控制每一圈里每一條邊遍歷的長度offset++;}if (n % 2) {res[mid][mid] = count;}return res;}
};// 輸出二維數組
void PrintVector(vector<vector<int>>& nums) {cout << "[ ";for (int i = 0; i < nums.size();i++) {cout << "[ ";for (int j = 0; j < nums.size(); j++) {cout << nums[i][j];if (j < nums.size() - 1) {cout << ", ";}		}cout << " ]";if (i < nums.size() - 1) {cout << ", ";}}cout << " ]" << endl;
}int main() {int n;cout << "請輸入正整數 n = " << endl;cin >> n;Solution obj;// 創建一個Solution類型的對象obj，vector<vector<int>> result;//通過obj對象調用generateMatrix函數，并傳入參數nresult = obj.generateMatrix(n);// 輸出結果cout << "螺旋矩陣為： " << endl;PrintVector(result);return 0;
}

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