算法：數組part02: 209. 長度最小的子數組 + 59.螺旋矩陣II+ 代碼隨想錄補充58.區間和 + 44. 開發商購買土地
209. 長度最小的子數組
題目：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
文章講解：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://www.bilibili.com/video/BV1tZ4y1q7XE（思想較難，看視頻復習）
思想
- 找出長度最小的子數組，用暴力解法，兩層for循環列出所有的可能情況（以i為頭以j為尾，這樣i從頭遍歷到尾，找到以數組所以元素為頭的子數組）可以解題；
- 要想用一層for實現上面的效果，就需要用到滑動窗口（雙指針）的思想，for循環滑動窗口的右邊界，左邊界在這層for的邏輯中去修改；就可以達到O(n)的時間復雜度；
解題
暴力解法
//C++版
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;}
};
正解
class Solution {public int minSubArrayLen(int target, int[] nums) {//利用滑動窗口（左右指針指示滑動窗口兩端，本身還是雙指針的思想）int left=0;int sum=0;//初始的result需要設為整數的最大值int result=Integer.MAX_VALUE;//記錄滿足條件的子串長度int sublength=0;for(int right=0;right<nums.length;right++){sum+=nums[right];while(sum>=target){sublength=right-left+1;result=Math.min(sublength,result);sum-=nums[left++];}}return result==Integer.MAX_VALUE?0:result;}
}////這個是參考答案，要更好理解，上面的是我寫的
class Solution {// 滑動窗口public int minSubArrayLen(int s, int[] nums) {int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= s) {result = Math.min(result, right - left + 1);sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}
總結
for循環循環的是滑動窗口的右邊界，左邊界在這個循環邏輯的內部利用while()去改變;感覺這個思想要記下來，第一次接觸基本想不出；
59.螺旋矩陣II
題目：https://leetcode.cn/problems/spiral-matrix-ii/description/
文章鏈接：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
思想
文章中總結的思路很好,要堅持循環不變量的原則：搞清區間的邊界，以及每次循環的判斷條件要一樣；
邊界確定：每行或每列的末尾不屬于本行，而作為下一行的開始
螺旋矩陣的n：n為偶數loop=2/n，n為奇數就需要單獨處理最內部的一個位置；
解題
class Solution {public int[][] generateMatrix(int n) {int nums[][]=new int[n][n];//循環圈數int loop=0;int startX=0;int startY=0;int i,j;//用來表示每行最后幾個不包含int offset=1;//用來表示填充的數字int count=1;int mid=n/2;while(loop<n/2){//下面的四個for就是模擬轉了一圈//首先是左上到右上for(j=startY;j<n-offset;j++){nums[startX][j]=count++;}//右上到右下for(i=startX;i<n-offset;i++){nums[i][j]=count++;}//右下到左下for(;j>startY;j--){nums[i][j]=count++;}//左下到左上for(;i>startX;i--){nums[i][j]=count++;}startX++;startY++;loop++;offset++;}//奇數的情況單獨給中間元素賦值if(n%2!=0){nums[mid][mid]=count;}return nums;}
}////這個是參考答案，要更好理解，上面的是我寫的
class Solution {public int[][] generateMatrix(int n) {int[][] nums = new int[n][n];int startX = 0, startY = 0; // 每一圈的起始點int offset = 1;int count = 1; // 矩陣中需要填寫的數字int loop = 1; // 記錄當前的圈數int i, j; // j 代表列, i 代表行;while (loop <= n / 2) {// 頂部// 左閉右開，所以判斷循環結束時， j 不能等于 n - offsetfor (j = startY; j < n - offset; j++) {nums[startX][j] = count++;}// 右列// 左閉右開，所以判斷循環結束時， i 不能等于 n - offsetfor (i = startX; i < n - offset; i++) {nums[i][j] = count++;}// 底部// 左閉右開，所以判斷循環結束時， j != startYfor (; j > startY; j--) {nums[i][j] = count++;}// 左列// 左閉右開，所以判斷循環結束時， i != startXfor (; i > startX; i--) {nums[i][j] = count++;}startX++;startY++;offset++;loop++;}if (n % 2 == 1) { // n 為奇數時，單獨處理矩陣中心的值nums[startX][startY] = count;}return nums;}
}總結
- 螺旋矩陣II的關鍵點在于循環不變量：確定邊界，循環條件不變；
- 時間復雜度為O(n2);
代碼隨想錄補充58.區間和
題目+講解：https://www.programmercarl.com/kamacoder/0058.%E5%8C%BA%E9%97%B4%E5%92%8C.html
思想
- 暴力解法:直接遍歷相應區間，計算總和的值，時間復雜度為O(m*n);
- 最優解：空間換時間，用一個新數組，新數組的每個元素存儲給出數組前i位元素的和，用到時直接取相應的p[b]-p[a-1]即可；如果a=0，則結果直接為p[b]；
解題
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int[] vec=new int[n];int presum=0;//定義一個新數組，每個位置存前i位元素的和int[] p=new int[n];int sum=0;//為原始數組、新數組每個元素賦值for(int i=0;i<n;i++){vec[i]=scanner.nextInt();presum+=vec[i];p[i]=presum;}//scanner.hashNextInt()用來判斷輸入是否還有下一個元素：即是否還需要求區間和while(scanner.hashNextInt()){int a=scanner.nextInt();int b=scanner.nextInt();if(a==0){sum=p[b];}else{sum=p[b]-p[a-1];}System.out.println(sum);}scanner.close();}
}////這個是參考答案，要更好理解，上面的是我寫的
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] vec = new int[n];int[] p = new int[n];int presum = 0;for (int i = 0; i < n; i++) {vec[i] = scanner.nextInt();presum += vec[i];p[i] = presum;}while (scanner.hasNextInt()) {int a = scanner.nextInt();int b = scanner.nextInt();int sum;if (a == 0) {sum = p[b];} else {sum = p[b] - p[a - 1];}System.out.println(sum);}scanner.close();}
}
總結
- 區間和思想其實很好理解：就是犧牲空間先存儲前i位的和，后面做減法就好；
44. 開發商購買土地
思想：
暴力解法即利用三層for循環，第一層分別遍歷橫向的n-1個分割線和縱向的m-1個分割線，剩下兩層for用來求總和；時間復雜度為O(n3)
優化解法：（1）用區間和的思想，先用新數組1存橫向前i行元素的總和，再用新數組2存縱向前i行元素的總和；（2）也可以用優化暴力解法來代替三層for;時間復雜度O(n2)
解題
//暴力
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];// 輸入區塊權值for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scanner.nextInt();}}int minDiff = Integer.MAX_VALUE;// 1. 枚舉所有橫向分割線（i 從 0 到 n-2）for (int i = 0; i < n - 1; i++) {int sumA = 0;int sumB = 0;// 計算上半部分（A 區域）的總和for (int x = 0; x <= i; x++) {for (int y = 0; y < m; y++) {sumA += grid[x][y];}}// 計算下半部分（B 區域）的總和for (int x = i + 1; x < n; x++) {for (int y = 0; y < m; y++) {sumB += grid[x][y];}}int diff = Math.abs(sumA - sumB);if (diff < minDiff) {minDiff = diff;}}// 2. 枚舉所有縱向分割線（j 從 0 到 m-2）for (int j = 0; j < m - 1; j++) {int sumA = 0;int sumB = 0;// 計算左半部分（A 區域）的總和for (int x = 0; x < n; x++) {for (int y = 0; y <= j; y++) {sumA += grid[x][y];}}// 計算右半部分（B 區域）的總和for (int x = 0; x < n; x++) {for (int y = j + 1; y < m; y++) {sumB += grid[x][y];}}int diff = Math.abs(sumA - sumB);if (diff < minDiff) {minDiff = diff;}}System.out.println(minDiff);}
}//區間和思想
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int sum = 0;int[][] vec = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {vec[i][j] = scanner.nextInt();sum += vec[i][j];}}// 統計橫向int[] horizontal = new int[n];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {horizontal[i] += vec[i][j];}}// 統計縱向int[] vertical = new int[m];for (int j = 0; j < m; j++) {for (int i = 0; i < n; i++) {vertical[j] += vec[i][j];}}int result = Integer.MAX_VALUE;int horizontalCut = 0;for (int i = 0; i < n; i++) {horizontalCut += horizontal[i];result = Math.min(result, Math.abs((sum - horizontalCut) - horizontalCut));// 更新result。其中，horizontalCut表示前i行的和，sum - horizontalCut表示剩下的和，作差、取絕對值，得到題目需要的“A和B各自的子區域內的土地總價值之差”。下同。}int verticalCut = 0;for (int j = 0; j < m; j++) {verticalCut += vertical[j];result = Math.min(result, Math.abs((sum - verticalCut) - verticalCut));}System.out.println(result);scanner.close();}
}//暴力解法優化import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int sum = 0;int[][] vec = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {vec[i][j] = scanner.nextInt();sum += vec[i][j];}}int result = Integer.MAX_VALUE;int count = 0; // 統計遍歷過的行// 行切分for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {count += vec[i][j];// 遍歷到行末尾時候開始統計if (j == m - 1) {result = Math.min(result, Math.abs(sum - 2 * count));}}}count = 0;// 列切分for (int j = 0; j < m; j++) {for (int i = 0; i < n; i++) {count += vec[i][j];// 遍歷到列末尾時候開始統計if (i == n - 1) {result = Math.min(result, Math.abs(sum - 2 * count));}}}System.out.println(result);scanner.close();}
}
(KRaft 版本3.7.0))
