1、相向双指针
15.三数之和
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();int n=nums.length;//n在这里初始值不要动 在需要的地方使用 n-1 或 n-2Arrays.sort(nums);for(int i=0;i<n-2;i++){//一定要想好i的范围 这里后续要考虑不与jk冲突 故为n-2int x=nums[i];int j=i+1,k=n-1;if(n<3){return result;}if(i>0&&x==nums[i-1]){continue;//这里不能手动加i++;for(int i=0; i<n-2; i++) 这个 for 循环,在每一次迭代结束时,都会自动帮你执行一次 i++,if 语句块中,不能手动执行了一次 i++}if(x+nums[i+1]+nums[i+2]>0){//i的范围循环条件中要设置成i-2 不然这里会越界break;}if(x+nums[n-1]+nums[n-2]<0){continue;}while(j<k){int s=x+nums[j]+nums[k];if(s>0){k--;}else if(s<0){j++;}else{result.add(Arrays.asList(x, nums[j], nums[k]));//找到解j++;//寻找下一个可能while(j<k&&nums[j]==nums[j-1]){//避免下一个解和尚一个重复 重复就跳过j++;}k--;while(j<k&&nums[k]==nums[k+1]){k--;} }}}return result;//一定要注意 要返回多组数组 返回值是一个列表}
}
1、为什么用双层list
-
内层
List<Integer>
:用来定义一个解的数据结构。 -
外层
List<>
:用来充当容器,收集所有找到的解。
2、Arrays.asList()的作用
Arrays.asList("A", "B", "C")
也是一个表达式。它是一个方法调用,执行后会返回一个结果——也就是一个内容为 ["A", "B", "C"]
的 List
对象。
3、创建空的可变列表 、增、删
List<String> list = new ArrayList<>();
增 (Add / 添加元素)
list.add(element)
: 在列表末尾添加一个元素。list.add(index, element)
: 在指定索引位置插入一个元素,后续元素向后移动。
删 (Remove / 删除元素)
list.remove(index)
: 根据索引删除元素,并返回被删除的元素。list.remove(Object element)
: 删除列表中第一个匹配的元素,成功则返回true
。
167.两数之和 二-输入有序数组
给你一个下标从 1 开始的整数数组 numbers
,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target
的两个数。如果设这两个数分别是 numbers[index1]
和 numbers[index2]
,则 1 <= index1 < index2 <= numbers.length
。
以长度为 2 的整数数组 [index1, index2]
的形式返回这两个整数的下标 index1
和 index2
。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:
输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
class Solution {public int[] twoSum(int[] numbers, int target) {int n=numbers.length;int x=0;int left=0,right=n-1;//左右角标为l和rwhile (left<right){x=numbers[left]+numbers[right];if(x>target){right--;}else if(x<target){left++;}else{break;}}return new int[]{left+1,right+1};//下标从1开始}
}
11.盛最多水的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1
提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
class Solution {public int maxArea(int[] height) {#时间复杂度 O(n)#空间复杂度O(1)int n=height.length;int ans=0;int left=0;int right=n-1;while(left<right){int area=(right-left)*Math.min(height[left],height[right]);ans=Math.max(ans,area);if(height[left]<height[right]){left++;}else{right--;}}return ans;}
}
max min函数
Math.max() Math.min()
42.接雨水
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
方法一、前后缀分解
class Solution {public int trap(int[] height) {#时间复杂度O(n)#空间复杂度O(n)int n=height.length;int[] pre_max=new int[n];//写数组长度 如果知道具体值就{1,2,3,4,5}pre_max[0]=height[0];for(int i=1;i<n;i++){pre_max[i]=Math.max(pre_max[i-1],height[i]);}int[] suf_max=new int[n];suf_max[n-1]=height[n-1];for(int j=n-2;j>-1;j--){suf_max[j]=Math.max(suf_max[j+1],height[j]);}int ans=0;for(int i=0;i<n;i++){ans+=Math.min(pre_max[i],suf_max[i])-height[i];}return ans;}
}
方法二、相向双指针
class Solution {public int trap(int[] height) {int n=height.length;int ans=0;int left=0,right=n-1;int pre_max=0;int suf_max=0;while(left<=right){//不是<,相等的还可以计算储水容量pre_max=Math.max(pre_max,height[left]);suf_max=Math.max(suf_max,height[right]);if(pre_max<suf_max){ans+=pre_max-height[left];left++;}else{ans+=suf_max-height[right];right--;}}return ans;}
}
总结与对比
特性 | 方法一 (前后缀分解) | 方法二 (相向双指针) |
---|---|---|
核心思想 | 对每个位置,预计算其全局的左、右最高墙。 | 对每个位置,通过比较两侧已知的最高墙,确定其储水量的“短板”。 |
时间复杂度 | O(n) (三次遍历) | O(n) (一次遍历) |
空间复杂度 | O(n) | O(1) |
优点 | 逻辑非常直观,分步清晰,容易理解和实现。 | 空间效率极高,代码更紧凑,性能略好。 |
缺点 | 需要额外的 O(n) 空间,当输入规模巨大时可能成为瓶颈。 | 逻辑相对抽象,初次理解可能需要花些时间思考。 |
2、滑动窗口
209.长度最小的子数组
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0
。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
class Solution {public int minSubArrayLen(int target, int[] nums) {//时间复杂度O(n)//空间复杂度O(1)int n=nums.length;int ans=n+1;//方便后面取minint left=0;int s=0;for(int right=0;right<n;right++){//先想右移 再在每次移动判断左端点int x=nums[right];s+=x;while(s-nums[left]>=target){//是s-nums[left]>=target不是s>=targets-=nums[left];//ans--;错误的 左端右移不代表ans一定变小left++;}if(s>=target){ans=Math.min(ans,right-left+1);}}return ans==n+1?0:ans;//三元运算符 没有if 这个函数直接返回得数 放在return后面}
}
您好,这个在 Java 中被称为 三元运算符 (Ternary Operator),也叫 条件运算符 (Conditional Operator)。
它是一种非常简洁的 if-else
语句的缩写形式。
三元运算符
它的基本语法是:
condition ? value_if_true : value_if_false
- condition:一个布尔表达式,其结果为
true
或false
。 - value_if_true:如果
condition
为true
,则整个表达式的结果就是这个值。 - value_if_false:如果
condition
为false
,则整个表达式的结果就是这个值。
713.乘积小于K的子数组
给你一个整数数组 nums
和一个整数 k
,请你返回子数组内所有元素的乘积严格小于 k
的连续子数组的数目。
示例 1:
输入:nums = [10,5,2,6], k = 100
输出:8
解释:8 个乘积小于 100 的子数组分别为:[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
示例 2:
输入:nums = [1,2,3], k = 0
输出:0
提示:
1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {if(k<=1) return 0;//边界处理情况 真的很重要 一定要优先考虑int n=nums.length;int ans=0;int left=0;int prod=1;for(int right=0;right<n;right++){prod*=nums[right];while(prod>=k){prod/=nums[left];left++;}// 对于固定的 right,有 right-left+a1 个合法的左端点ans+=right-left+1;//尽量放在第二层循环后 第一层循环结束直接计算 结果不合理}return ans;}
}
3、二分查找
34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
闭区间写法
left = 0;
right = n - 1;
while (left <= right)
right = mid - 1;
left = mid + 1;
return left;
class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums, target);if (start == nums.length || nums[start] != target) {return new int[]{-1, -1}; // nums 中没有 target}// 如果 start 存在,那么 end 必定存在int end = lowerBound(nums, target + 1) - 1;return new int[]{start, end};}// lowerBound 返回最小的满足 nums[i] >= target 的下标 i// 如果数组为空,或者所有数都 < target,则返回 nums.length// 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]private int lowerBound(int[] nums, int target) {int left = 0;int right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量:// nums[left-1] < target// nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1; // 范围缩小到 [left, mid-1]} else {left = mid + 1; // 范围缩小到 [mid+1, right]}}// 循环结束后 left = right+1// 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target// 所以 left 就是第一个 >= target 的元素下标return left;}
}
左闭右开区间写法
left = 0;
right = n;
while (left < right)
right = mid;
left = mid + 1;
return left;
class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums, target);if (start == nums.length || nums[start] != target) {return new int[]{-1, -1}; // nums 中没有 target}// 如果 start 存在,那么 end 必定存在int end = lowerBound(nums, target + 1) - 1;return new int[]{start, end};}// lowerBound 返回最小的满足 nums[i] >= target 的下标 i// 如果数组为空,或者所有数都 < target,则返回 nums.length// 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]private int lowerBound(int[] nums, int target) {int left = 0;int right = nums.length; // 左闭右开区间 [left, right)while (left < right) { // 区间不为空// 循环不变量:// nums[left-1] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid; // 范围缩小到 [left, mid)} else {left = mid + 1; // 范围缩小到 [mid+1, right)}}// 循环结束后 left = right// 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target// 所以 left 就是第一个 >= target 的元素下标return left;}
}
开区间写法(最推荐 简单好记)
left=-1;
right=n;
while(left+1<right)
left=m;
right=m;
return right;
class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums, target);if (start == nums.length || nums[start] != target) {return new int[]{-1, -1}; // nums 中没有 target}// 如果 start 存在,那么 end 必定存在int end = lowerBound(nums, target + 1) - 1;return new int[]{start, end};}// lowerBound 返回最小的满足 nums[i] >= target 的下标 i// 如果数组为空,或者所有数都 < target,则返回 nums.length// 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]private int lowerBound(int[] nums, int target) {int left = -1;int right = nums.length; // 开区间 (left, right)while (left + 1 < right) { // 区间不为空// 循环不变量:// nums[left] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid; // 范围缩小到 (left, mid)} else {left = mid; // 范围缩小到 (mid, right)}}// 循环结束后 left+1 = right// 此时 nums[left] < target 而 nums[right] >= target// 所以 right 就是第一个 >= target 的元素下标return right;}
}
162.寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums
,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞
。
你必须实现时间复杂度为 O(log n)
的算法来解决此问题。
示例 1:
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;或者返回索引 5, 其峰值元素为 6。
提示:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
- 对于所有有效的
i
都有nums[i] != nums[i + 1]
class Solution {public int findPeakElement(int[] nums) {int n=nums.length;int left=0;int right=n-1;while(left<right){int m=(right+left)>>>1;if(nums[m]<nums[m+1]){//m 肯定不是峰值,峰值在右边。left=m+1;}else{//m 可能就是峰值,或者峰值在 m 的左边。right=m;}}return right;}
}
153.寻找旋转排序数组中的最小值
左闭右开
class Solution {public int findMin(int[] nums) {int n = nums.length;int left = 0;int right = n;while(left<right){int m=(right+left)>>>1;if(nums[m]>nums[n-1]){left=m+1;}else{right=m;}}return nums[left];}
}
左开右闭
class Solution {public int findMin(int[] nums) {int n = nums.length;int left = -1;int right = n - 1; // 开区间 (-1, n-1)while (left + 1 < right) { // 开区间不为空int mid = (left + right) >>> 1;if (nums[mid] < nums[n - 1]) {right = mid;} else {left = mid;}}return nums[right];}
}
33.搜索旋转排序数组
整数数组 nums
按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 向左旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
下标 3
上向左旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums
和一个整数 target
,如果 nums
中存在这个目标值 target
,则返回它的下标,否则返回 -1
。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums
中的每个值都 独一无二- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 -104 <= target <= 104
- 左开右闭写法
class Solution {public int search(int[] nums, int target) {int n=nums.length;int last=nums[n-1];int left=-1;int right=n;while(left+1<right){int m=(left+right)>>>1;if(nums[m]<=last&&last<target){//蓝target第一段 mid第二段right=m;}else if(nums[m]>last&&last>=target){//红target在第二段 mid在第一段left=m;}else{if(nums[m]<target){//红 同一段left=m;}else{right=m;}}}return nums[right] == target ? right : -1;}
}
4、二维数组
59. 螺旋矩阵 II
给你一个正整数 n
,生成一个包含 1
到 n2
所有元素,且元素按顺时针顺序螺旋排列的 n x n
正方形矩阵 matrix
。
示例 1:
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
示例 2:
输入:n = 1
输出:[[1]]
提示:
1 <= n <= 20
class Solution {public int[][] generateMatrix(int n) {int[][] ans=new int[n][n];int startx=0,starty=0;//每一圈的起始位置 角标 两个要分别赋值int offset=1;//让每一圈逐渐缩小int loop=1;//记录当前圈数int count=1;//遍历的数int i,j=0;//初始化不需要赋值 是因为后面会在循环内赋值while(loop<=n/2){// 顶部// 左闭右开,所以判断循环结束时, j 不能等于 n - offsetfor(j=startx;j<n-offset;j++){//第一遍是遍历列数 所以用j j=startx而不是0ans[startx][j]=count++;//j 永远是它进入本次循环时的那个值。j++ 的效果要到下一次循环判断条件时才会体现出来} // 右列// 左闭右开,所以判断循环结束时, i 不能等于 n - offsetfor(i=starty;i<n-offset;i++){ans[i][j]=count++;}// 底部// 左闭右开,所以判断循环结束时, j != startYfor(;j>starty;j--){ans[i][j]=count++;}// 左列// 左闭右开,所以判断循环结束时, i != startXfor(;i>startx;i--){ans[i][j]=count++;}startx++;starty++;loop++;offset++;}if(n%2==1){ans[startx][starty]=count;}return ans;}
}
在 ans[startx][j] = count++;
这行代码中,j
永远是它进入本次循环时的那个值。j++
的效果要到下一次循环判断条件时才会体现出来。
5、区间和
58.区间和(第九期模拟笔试)卡码网
[题目解析](58. 区间和 | 代码随想录)
题目描述
给定一个整数数组 Array,请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n,接下来 n 行,每行一个整数,表示数组的元素。随后的输入为需要计算总和的区间下标:a,b (b > = a),直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
提示信息
数据范围:
0 < n <= 100000
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];//前i项和int presum=0;for(int i=0;i<n;i++){vec[i]=scanner.nextInt();//从键盘输入读取一个整数presum+=vec[i];p[i]=presum;//前i项和}while(scanner.hasNextInt()){//检查是否还有下一个整数输入int l=scanner.nextInt();int r=scanner.nextInt();int sum=0;if(l==0){sum=p[r];}else{sum=p[r]-p[l-1];}System.out.println(sum);}scanner.close();}
}
Scanner
import java.util.Scanner;
- 作用: "导入"
Scanner
工具。Scanner
是 Java 标准库里提供的一个工具类,在使用前需要先像这样告诉编译器:“嘿,我准备用Scanner
这个东西了!”
Scanner scanner = new Scanner(System.in);
- 作用: 创建一个
Scanner
对象。 new Scanner(System.in)
就是在创建一个新的“接收器”,并把它对准键盘。Scanner scanner = ...
是给这个接收器起个名字,叫做scanner
,方便后面使用。
int n = scanner.nextInt();
- 作用: 读取一个整数。
- 程序运行到这里会暂停,等待你从键盘输入一个整数然后按回车。
scanner
会捕获这个输入,把它转换成int
类型,然后赋值给变量n
。
while (scanner.hasNextInt()) { ... }
- 作用: 检查是否还有下一个整数输入。
- 这是一个非常常用的循环方式。
scanner.hasNextInt()
会检查输入流中是否还有一个整数。 - 如果用户继续输入整数,它就返回
true
,循环继续;如果用户输入了非数字(或者在某些环境下按下了Ctrl+D
或Ctrl+Z
来表示输入结束),它就返回false
,循环终止。
scanner.close();
- 作用: 关闭
Scanner
。 - 这是一个好习惯。当你用完
Scanner
后,调用close()
方法可以释放它占用的资源。就像你用完电器要关掉电源一样。
44.开发商购买土地(第五期模拟笔试)卡码网
[题目链接](44. 开发商购买土地 | 代码随想录)
题目描述
在一个城市区域内,被划分成了n * m个连续的区块,每个区块都拥有不同的权值,代表着其土地价值。目前,有两家开发公司,A 公司和 B 公司,希望购买这个城市区域的土地。
现在,需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而,由于城市规划的限制,只允许将区域按横向或纵向划分成两个子区域,而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争,你需要找到一种分配方式,使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意:区块不可再分。
输入描述
第一行输入两个正整数,代表 n 和 m。
接下来的 n 行,每行输出 m 个正整数。
输出描述
请输出一个整数,代表两个子区域内土地总价值之间的最小差距。
输入示例
3 3
1 2 3
2 1 3
1 2 3
输出示例
0
提示信息
如果将区域按照如下方式划分:
1 2 | 3
2 1 | 3
1 2 | 3
两个子区域内土地总价值之间的最小差距可以达到 0。
数据范围:
1 <= n, m <= 100;
n 和 m 不同时为 1。
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;//MAX_VALUE是Java中一个 int 变量所能存储的最大正数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();}
}