今天，帶來數(shù)組相關(guān)算法的講解。文中不足錯(cuò)漏之處望請(qǐng)斧正！

理論基礎(chǔ)點(diǎn)這里

---

有序數(shù)組的平方

給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序。

示例 1：

輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]
排序后，數(shù)組變?yōu)?[0,1,9,16,100]
示例 2：

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

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非遞減順序 排序

進(jìn)階：

請(qǐng)你設(shè)計(jì)時(shí)間復(fù)雜度為 O(n) 的算法解決本問題

1. 思路

只有正數(shù)時(shí)，平方的大小就是從頭到尾即由小到大。

那順序遍歷升序數(shù)組，作平方，就能得到升序結(jié)果。

但有負(fù)數(shù)時(shí)該怎么辦？最小的平方應(yīng)該是從兩端趨向中間的最接近0的那個(gè)值。

從這個(gè)值往兩邊走，誰的平方大，誰就先插入結(jié)果集。題目要求升序，那我們就從結(jié)果集的尾部到結(jié)果集的頭部放入結(jié)果。

要“往兩邊走”我們用雙指針從兩邊遍歷就好啦，誰大誰先插入結(jié)果數(shù)組。

2. 參考代碼

class Solution {
public:// 找0, 雙指針從兩頭向中間找, 平方和大的插入結(jié)果集的后面vector<int> sortedSquares(vector<int>& nums) {vector<int> result(nums.size());int left = 0;int right = nums.size() - 1;int insertIndex = result.size() - 1;while (left <= right) { // left==righrt時(shí), nums[left]的平方和也要插入結(jié)果集long long squre1 = pow(nums[left], 2);long long squre2 = pow(nums[right], 2);if (squre1 > squre2) {result[insertIndex--] = squre1;++left;} else {result[insertIndex--] = squre2;--right;}}return result;}
};

長(zhǎng)度最小的子數(shù)組

1. 思路

理解題意

分析如何滿足需求

1.1 暴力遍歷

兩層for，一個(gè)指針確定當(dāng)前想遍歷的區(qū)間的起始位置，另一個(gè)指針遍歷來確定終止位置，把所有可能的區(qū)間都遍歷一遍，一旦區(qū)間和大于target，就對(duì)比并取最小的長(zhǎng)度。

參考代碼如下：

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int minLen = INT_MAX;int sum = 0; // 子序列的數(shù)值之和int subLength = 0; // 子序列的長(zhǎng)度for (int i = 0; i < nums.size(); i++) { // 設(shè)置子序列起點(diǎn)為isum = 0;for (int j = i; j < nums.size(); j++) { // 設(shè)置子序列終止位置為jsum += nums[j];if (sum >= s) { // 一旦發(fā)現(xiàn)子序列和超過了s，更新resultsubLength = j - i + 1; // 取子序列的長(zhǎng)度result = result < subLength ? result : subLength;break; // 因?yàn)槲覀兪钦曳蠗l件最短的子序列，所以一旦符合條件就break，不要再累加元素了}}}return result == INT_MAX ? 0 : result;}
};

1.2 滑動(dòng)窗口

暴力的方法比較死板：直接把所有可能得區(qū)間都遍歷一遍。每一次都是靜態(tài)確認(rèn)好一個(gè)區(qū)間 [i, j] ，再累加求結(jié)果，有沒有辦法更靈活地確認(rèn)這個(gè)連續(xù)子數(shù)組地區(qū)間呢？有的。

我們可以維護(hù)一個(gè)連續(xù)子數(shù)組的區(qū)間（右邊的指針固定走，左邊的指針能跟就跟，保證長(zhǎng)度最小），——滑動(dòng)窗口。

什么是滑動(dòng)窗口？其實(shí)是雙指針的一種應(yīng)用，兩個(gè)指針動(dòng)態(tài)移動(dòng)，維護(hù)一個(gè)區(qū)間，像滑動(dòng)的窗口一樣。

滑動(dòng)窗口在本題中怎么用呢？

為什么是end固定往后走，begin根據(jù)策略走？

首先，end必須把整個(gè)數(shù)組遍歷一遍；其次，begin作為起始位置，不一定需要固定走（如果區(qū)間和不大于等于target，走了有什么意義呢）。

end遍歷給定數(shù)組nums，當(dāng)區(qū)間和大于target的時(shí)候，就得到了當(dāng)前最小的連續(xù)子序列，但不是最終的。所以在end往后移動(dòng)的時(shí)候，begin也要根據(jù)一定策略追趕end，保證得到最終的最小連續(xù)子序列。

begin到底是怎樣移動(dòng)的呢？

• 如果當(dāng)前區(qū)間是連續(xù)子數(shù)組，begin就要移動(dòng)
• 如果當(dāng)前區(qū)間不是連續(xù)子數(shù)組，那么begin就不能移動(dòng)

這樣子移動(dòng)，每次begin移動(dòng)完，[begin, end]的和都會(huì)小于target（不再是連續(xù)子數(shù)組），但這不影響，因?yàn)樵谒詈筮€是連續(xù)子數(shù)組的時(shí)候，我們已經(jīng)用minLen記錄了它的長(zhǎng)度。這樣走下去，就能獲取到最短的長(zhǎng)度。

2. 參考代碼

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int begin = 0; // [begin, end] 就是期望的最短子數(shù)組區(qū)間int end = 0;int curLen = 0;int minLen = INT_MAX;long long sum = 0;while (end < nums.size()) {sum += nums[end];while (sum >= target) { // 已經(jīng)是子數(shù)組, 開始縮減長(zhǎng)度curLen = end - begin + 1;minLen = min(curLen, minLen);sum -= nums[begin++]; // 縮減長(zhǎng)度}++end;}return minLen == INT_MAX ? 0 : minLen;}
};

---

今天的分享就到這里了，感謝您能看到這里。

這里是培根的blog，期待與你共同進(jìn)步！