算法：数组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))
