今日題目：

• 977. 有序數組的平方 | LeetCode
• 209. 長度最小的子數組 | LeetCode
• 76. 最小覆蓋子串 | LeetCode
• 59. 螺旋矩陣 II | LeetCode

今日總結

今天繼續做的《數組》系列的題目，其中最重要的是學習滑動窗口法，學會了滑動窗口的代碼框架思路，并借助兩道題目來學習利用這個框架代碼來解決具體問題，這是重點要掌握的。

除此之外，還解決了另外兩道題，其中“有序數組平方”這道題鍛煉了我對雙指針法的靈活運行，學習到了在使用雙指針時，選擇一個好的行進方向可以避免對很多臨界情況的判斷，從而減少代碼復雜度避免出錯。

Problem 1：有序數組平方 ???

977. 有序數組的平方 | LeetCode

這個題考驗對“雙指針”的靈活運用，不能死板。

最開始的做法是先找到第一個非負整數和最大負數，然后從中間向兩邊逐個比較得出結果，但這樣的缺點是需要判斷大量的臨界條件，這很容易就產生錯誤，所以應該換一個思路。

在這里需要轉換一個思路，不要從中間向兩邊走，而是從兩邊向中間走，從而利用雙指針。這樣在 while 中判斷終止條件就只需要是 left 和 right 有沒有碰上了。

這個題目最簡單的方法就是，讓 left 指向 0，right 指向末尾，然后兩個指針逐漸向中間移動，每次將最大的放到結果集中：

class Solution {public int[] sortedSquares(int[] nums) {List<Integer> result = new ArrayList<>();int left = 0, right = nums.length - 1;while (!(left > right)) {  // 直到 left 和 right 碰上int leftValue = nums[left] * nums[left];int rightValue = nums[right] * nums[right];if (leftValue < rightValue) {result.add(rightValue);right--;} else {result.add(leftValue);left++;}}Collections.reverse(result);return result.stream().mapToInt(Integer::valueOf).toArray();}
}

因為這里是每次讓平方值大的移動，當 left 或 right 走到中間絕對值是最小值的數字后就不會再移動了，所以不用擔心 left 會超過負數范圍或者 right 超過正數范圍。我的一次 commit 就因為擔心這個而多寫了很多判斷條件。

總結的經驗是，利用好題目的特性和性質，選擇好雙指針的移動方向，盡量減少對臨界條件的判斷，從而減小代碼復雜度。

Problem 2：滑動窗口法 【必會】

這個方法是個通用的方法，用于解決子串問題。

參考 labuladong 的講解，滑動窗口的代碼框架如下：

int left = 0, right = 0;while (left < right && right < s.size()) {// 增大窗口window.add(s[right]);right++;// 更新相關數據 ......while (window needs shrink) {// 縮小窗口（在這之前可能需要記錄一下解）window.remove(s[left]);left++;// 更新相關數據 ......}
}

具體的講解可以參考 labuladong 的文章。這里使用這個思路來解決 LeetCode 中 209 和 76 兩個題目。重要是通過這幾個題目來理解如何利用上面這個滑動窗口框架來解決具體的問題。

LeetCode 209. 長度最小的子數組 Medium

209. 長度最小的子數組 | LeetCode

這個題可以經典地套用上面的框架，解題代碼如下：

class Solution {public int minSubArrayLen(int target, int[] nums) {int low = 0, high = 0;int sum = 0;int minLen = nums.length;int curLen = 0;boolean found = false;while (high < nums.length) {// 擴大右窗口sum += nums[high];high++;// 更新相關數據curLen++;while (sum >= target) {// 記錄解found = true;if (curLen < minLen) {minLen = curLen;}// 收縮左窗口sum -= nums[low];low++;// 更新相關數據curLen--;}}return found? minLen: 0;}
}

LeetCode 76. 最小覆蓋子串 Hard

這個題雖然很難，但仍然能夠套用上面介紹的滑動窗口框架，需要額外處理的就是一些條件的檢查等問題。

通過這個題，可以很好地鍛煉如何套用之前滑動窗口框架代碼。

關于這個題的講解，可以參考 labuladong 文章中的講解。

Problem 3：螺旋矩陣 II 【還行】

59. 螺旋矩陣 II | LeetCode

這個題目還行，比較偏技巧，抓住問題的要點：“方向的改變是固定的，也就是向右走的下一個方向一定是向下走”，所以我們需要確定好什么時候發生方向的轉變。

這個題目在 LeetCode 中題解所介紹的有點麻煩，這里我的關鍵實現是實現一個 next() 函數，這個函數根據當前的方向和位置，確定出下一個走到的位置。確定下一個位置的思路是：判斷一下當前方向能不能繼續向下走，不能走的話就轉變方向。

代碼實現：

class Solution {int row;  // 當前位置的行號int col;  // 當前位置的列號int direction;  // 當前移動的方向public int[][] generateMatrix(int n) {row = 0;col = 0;direction = 1;int[][] matrix = new int[n][n];int square = n * n;for (int i = 1; i <= square; i++) {matrix[row][col] = i;if (i != square) {next(matrix, n);}}return matrix;}// 根據當前的方向和位置，確定下一個移動到的位置private boolean next(int[][] matrix, int n) {if (direction == 1) {  // 向右走if (col + 1 < n && matrix[row][col + 1] == 0) {  // 判斷是否能繼續按這個方向走col += 1;return true;} else {  // 不能繼續的話，就轉變方向direction = 2;return next(matrix, n);}}if (direction == 2) {  // 向下走if (row + 1 < n && matrix[row + 1][col] == 0) {row += 1;return true;} else {direction = 3;return next(matrix, n);}}if (direction == 3) {  // 向左走if (col - 1 >= 0 && matrix[row][col - 1] == 0) {col -= 1;return true;} else {direction = 4;return next(matrix, n);}}if (direction == 4) {  // 向上走if (row - 1 >= 0 && matrix[row - 1][col] == 0) {row -= 1;return true;} else {direction = 1;return next(matrix, n);}}return false;}}

• 關鍵就是這里的 next() 函數的實現