算法：数组part02: 209. 长度最小的子数组 + 59.螺旋矩阵II + 代码随想录补充58.区间和 + 44. 开发商购买土地

算法：数组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++) { // 设置子序列起点为i sum = 0; for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j sum += nums[j]; if (sum >= s) { // 一旦发现子序列和超过了s，更新result  subLength = 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 - offset for (j = startY; j < n - offset; j++) { nums[startX][j] = count++; } // 右列 // 左闭右开，所以判断循环结束时， i 不能等于 n - offset for (i = startX; i < n - offset; i++) { nums[i][j] = count++; } // 底部 // 左闭右开，所以判断循环结束时， j != startY for (; j > startY; j--) { nums[i][j] = count++; } // 左列 // 左闭右开，所以判断循环结束时， i != startX for (; i > startX; i--) { nums[i][j] = count++; } startX++; startY++; offset++; loop++; } if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值 nums[startX][startY] = count; } return nums; }}

总结

• 螺旋矩阵II的关键点在于循环不变量：确定边界，循环条件不变；
• 时间复杂度为O(n²);

代码随想录补充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(n³)
优化解法：（1）用区间和的思想，先用新数组1存横向前i行元素的总和，再用新数组2存纵向前i行元素的总和；（2）也可以用优化暴力解法来代替三层for;时间复杂度O(n²)

解题

//暴力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(); }}