【代码随想录——数组——二刷】

数组

1. 二分查找(704)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

1.1 二分法的第一种写法

我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
常规写法

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1
	var mid int
	for l<=r {
		mid  = (l+r)/2
		if nums[mid]==target{
			return mid
		}else if nums[mid]>target {
			r = mid-1
		}else{
			l = mid+1
		}
	}
	return -1
}

递归写法

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1
    return searchBinary(nums, target,l,r)
}

func searchBinary(nums []int,target,left,right int) int {
    if left>right{
        return -1
    }
    mid := (left+right)/2
    if nums[mid]==target{
        return mid
    }else if nums[mid]>target{
        return searchBinary(nums,target,left,mid-1)
    }else{
        return searchBinary(nums,target,mid+1,right)
    }
}

1.2 二分法的第二种写法

我们定义 target 是在一个在左闭右开的区间里，也就是[left, right)
常规写法

func search(nums []int, target int) int {
	l, r := 0, len(nums)
	var mid int
	for l<r {
		mid  = (l+r)/2
		if nums[mid]==target{
			return mid
		}else if nums[mid]>target {
			r = mid
		}else{
			l = mid+1
		}
	}
	return -1
}

递归写法

func search(nums []int, target int) int {
	l, r := 0, len(nums)
    return searchBinary(nums, target,l,r)
}

func searchBinary(nums []int,target,left,right int) int {
    if left>=right{
        return -1
    }
    mid := (left+right)/2
    if nums[mid]==target{
        return mid
    }else if nums[mid]>target{
        return searchBinary(nums,target,left,mid)
    }else{
        return searchBinary(nums,target,mid+1,right)
    }
}

1.3 相关题目推荐

1.3.1 搜索插入位置（35）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

func searchInsert(nums []int, target int) int {
    return findGEIndex(nums,target)
}

func findGEIndex(nums []int,target int) int{
    low,high := 0,len(nums)-1
    for low<=high{
        mid := low+(high-low)/2
        if nums[mid]>=target{
            high = mid-1
        }else{
            low = mid+1
        }
    }
    return low
}

1.3.2 在排序数组中查找元素的第一个和最后一个位置（34）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

func searchRange(nums []int, target int) []int {
	res := []int{-1, -1}
	if len(nums) == 0 {
		return res
	}
	right := FindGIndex(nums, target)
    //判断是否存在该元素
	if right-1<0 || nums[right-1] != target {
		return res
	} 
	left := FindLIndex(nums, target)
    res[0] = left + 1
    res[1] = right - 1
    return res
}

func FindGIndex(nums []int,target int)int{
    low,high,mid := 0,len(nums)-1,0
    for low<=high{
        mid = low+(high-low)/2
        if nums[mid]>target{
            high = mid-1
        }else{
            low = mid+1
        }
    }
    return low
}

func FindLIndex(nums []int,target int)int{
    low,high,mid := 0,len(nums)-1,0
    for low<=high{
        mid = low+(high-low)/2
        if nums[mid]<target{
            low = mid + 1
        }else{
            high = mid -1
        }
    }
    return high
}

1.3.3 X的平方根（69）

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

func mySqrt(x int) int {
    return binarySearch(x)
}

func binarySearch(target int) int{
    low,high,mid := 0,target,0
    for low<=high{
        mid = low+(high-low)/2
        pow_num := mid*mid
        if pow_num==target{
            return mid
        }else if pow_num>target{
            high = mid-1
        }else{
            low = mid+1
        }
    }
    if high*high<target{
        return high
    }else{
        return high-1
    }
    
}

1.3.4 有效的完全平方数（367）

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。

func isPerfectSquare(num int) bool {
    return binarySearch(num)
}

func binarySearch(target int) bool{
    low,high,mid := 0,target,0
    for low<=high{
        mid = low+(high-low)/2
        pow_num := mid*mid
        if pow_num==target{
            return true
        }else if pow_num>target{
            high = mid-1
        }else{
            low = mid+1
        }
    }
    return false    
}

2. 移除元素（27）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
快慢指针

func removeElement(nums []int, val int) int {
    fastPoint,slowPoint := 0,0
    for i:=0;i<len(nums);i++{
        if nums[i]==val{
            fastPoint++
        }else{
            nums[slowPoint] = nums[fastPoint]
            fastPoint++
            slowPoint++
        }
    }
    return len(nums)-(fastPoint-slowPoint)
}

2.1 移除排序数组中的重复项（26）

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

func removeDuplicates(nums []int) int {
    count,current := 1,nums[0]
    for i:=1;i<len(nums);i++{
        if nums[i]!=current{
            nums[count]=nums[i]
            current = nums[i]
            count++
        }
    }
    return count
}

2.2 移动零（283）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

func moveZeroes(nums []int)  {
    zeroNum,currentIndex := 0,0
    for i:=0;i<len(nums);i++{
        if nums[i]==0{
            zeroNum++
        }else{
            nums[currentIndex]= nums[i]
            currentIndex++
        }
        if zeroNum+currentIndex>len(nums){
            // 提前结束
            break
        }
    }
    for i:=len(nums)-zeroNum;i<len(nums);i++{
        nums[i]=0
    }
}

2.3 比较含退格的字符串（844）

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

func backspaceCompare(s string, t string) bool {
	return paresStr(s)==paresStr(t)
}

func paresStr(s string) string {
	r := []rune(s)
	currentIndex := 0
	for i := 0; i < len(r); i++ {
		if r[i] == '#' && currentIndex > 0 {
			currentIndex--
		}
		if r[i] != '#' {
			r[currentIndex] = r[i]
			currentIndex++
		}
	}
	return string(r[:currentIndex])
}

2.4 有序数组的平方（977）

如下

3. 有序数组的平方（977）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

3.1 不太雅观的代码

func sortedSquares(nums []int) []int {
	firstPositiveIndex := -1
	lengthOfNums := len(nums)
	for i := 0; i < lengthOfNums; i++ {
		if nums[i] > 0 {
			firstPositiveIndex = i
			break
		}
	}
	if firstPositiveIndex == -1 {
		//全是负数的处理
		for i := 0; i < (lengthOfNums+1)/2; i++ {
			temp := nums[i] * nums[i]
			nums[i] = nums[lengthOfNums-i-1] * nums[lengthOfNums-i-1]
			nums[lengthOfNums-i-1] = temp
		}
	} else if firstPositiveIndex == 0 {
		//全是正数的处理
		for i := 0; i < lengthOfNums; i++ {
			nums[i] = nums[i] * nums[i]
		}
	} else {
		var res []int
		left, right := firstPositiveIndex-1, firstPositiveIndex
		//全部先平方
		for i := 0; i < lengthOfNums; i++ {
			nums[i] = nums[i] * nums[i]
		}
		for left >= 0 && right < lengthOfNums {
			if nums[left] < nums[right] {
				res = append(res, nums[left])
				left--
			} else {
				res = append(res, nums[right])
				right++
			}
		}
		for left >= 0 {
			res = append(res, nums[left])
			left--
		}
		for right < lengthOfNums {
			res = append(res, nums[right])
			right++
		}
		return res
	}
	return nums
}

3.2 美观代码

func sortedSquares(nums []int) []int {
	firstPositiveIndex := -1
	lengthOfNums := len(nums)
	for i := 0; i < lengthOfNums; i++ {
		if nums[i] > 0 {
			firstPositiveIndex = i
			break
		}
	}
	if firstPositiveIndex == -1 {
		// 全是负数时
		reverse(nums, 0, lengthOfNums-1)
		return powOfArr(nums, 0, lengthOfNums-1)
	} else if firstPositiveIndex == 0 {
		// 全是正数
		return powOfArr(nums, 0, lengthOfNums-1)
	} else {
		reverse(nums, 0, firstPositiveIndex-1)
		arr1 := powOfArr(nums, 0, firstPositiveIndex-1)
		arr2 := powOfArr(nums, firstPositiveIndex, lengthOfNums-1)
		var res []int
		arr1Index, arr2Index := 0, 0
		for arr1Index < len(arr1) && arr2Index < len(arr2) {
			if arr1[arr1Index] < arr2[arr2Index] {
				res = append(res, arr1[arr1Index])
				arr1Index++
			} else {
				res = append(res, arr2[arr2Index])
				arr2Index++
			}
		}
		res = append(res, arr1[arr1Index:]...)
		res = append(res, arr2[arr2Index:]...)
		return res
	}
}

// [start,end]
func reverse(nums []int, start, end int) {
	var temp int
	for start < end {
		temp = nums[start]
		nums[start] = nums[end]
		nums[end] = temp
		start++
		end--
	}
}

// [start,end]
func powOfArr(nums []int, start, end int) []int {
	var res []int
	for i := start; i <= end; i++ {
		res = append(res, nums[i]*nums[i])
	}
	return res
}

3.3 优化（寻找第一个大于0的数的下标）

基于二分查找寻找第一个大于0的数的下标

// 查找大于等于 num 的第一个数的下标
func findFirstGeNumIndex(nums []int, num int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)/2
		if nums[mid] >= num {
			//保证了nums[high]最终一定小于num
			high = mid - 1
		} else {
			//low逐渐逼近大于等于num的第一个数的下标
			low = mid + 1
		}
	}
	if low < len(nums) && nums[low] >= num {
		return low
	}
	return -1 // 如果没有找到，返回 -1
}
// 查找大于 num 的第一个数的下标
func findFirstGNumIndex(nums []int, num int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)/2
		if nums[mid] > num {
			//保证了nums[high]最终一定小于等于num
			high = mid - 1
		} else {
			//low逐渐逼近大于num的第一个数的下标
			low = mid + 1
		}
	}
	if low < len(nums) && nums[low] >= num {
		return low
	}
	return -1 // 如果没有找到，返回 -1
}
// 查找小于等于 num 的第一个数的下标
func findFirstLeNumIndex(nums []int, num int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)/2
		if nums[mid] <= num {
			// 保证了nums[low]大于等于num
			low = mid + 1
		} else {
			// high逐渐逼近小于等于 num 的第一个数的下标
			high = mid - 1
		}
	}
	if high >= 0 && nums[high] <= num {
		return high
	}
	return -1 // 如果没有找到，返回 -1
}

// 查找小于 num 的第一个数的下标
func findFirstLNumIndex(nums []int, num int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)/2
		if nums[mid] < num {
			// 保证了nums[low]大于num
			low = mid + 1
		} else {
			// high逐渐逼近小于 num 的第一个数的下标
			high = mid - 1
		}
	}
	if high >= 0 && nums[high] < num {
		return high
	}
	return -1 // 如果没有找到，返回 -1
}

4. 长度最小的子数组（209）

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

快慢指针法

func minSubArrayLen(target int, nums []int) int {
	slow, fast, sum := 0, 0, 0
	minLen := math.MaxInt32
	for _, num := range nums {
		sum += num
		fast++
		if sum >= target {
			for sum >= target {
				sum -= nums[slow]
				slow++
			}
			if minLen > fast-slow+1 {
				minLen = fast - slow + 1
			}
		}
	}
	if minLen == math.MaxInt32 {
		return 0
	}
	return minLen
}

4.1 水果成篮（904）

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
  给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

4.1.1 简单的双重循环

在第90个测试用例超时了

func totalFruit(fruits []int) int {
    maxNum := 0
    for i:=0;i<len(fruits);i++{
        count := GetFruitFromIndex(fruits,i)
        if maxNum<count{
            maxNum=count
        }
    }
    return maxNum
}

func GetFruitFromIndex(fruits []int, index int)int{
    firstKind,secondKind := fruits[index],-1
    count := 1
    for i:=index+1;i<len(fruits);i++{
        if fruits[i]!=firstKind {
            if secondKind==-1{
                secondKind=fruits[i]
            }else if(secondKind!=fruits[i]){
                return count
            }
        }
        count++
    }
    return count
}

4.1.2 剪枝的双重循环

我们添加了一个剪枝操作，当我们获得的最大果子数大于剩下的所有树时，提前结束算法。

func totalFruit(fruits []int) int {
    maxNum := 0
    for i:=0;i<len(fruits);i++{
        count := GetFruitFromIndex(fruits,i)
        if maxNum<count{
            maxNum=count
        }
        // 剪枝操作
        if maxNum >= len(fruits)-i{
            return maxNum
        }
    }
    return maxNum
}

func GetFruitFromIndex(fruits []int, index int)int{
    firstKind,secondKind := fruits[index],-1
    count := 1
    for i:=index+1;i<len(fruits);i++{
        if fruits[i]!=firstKind {
            if secondKind==-1{
                secondKind=fruits[i]
            }else if(secondKind!=fruits[i]){
                return count
            }
        }
        count++
    }
    return count
}

4.1.3 滑动窗口（正解）

func totalFruit(fruits []int) int {
	lastFruit1Index, lastFruit2Index, count := 0, -1, 1
	fruit1, fruit2 := fruits[0], -1
	maxNum := 0
	for i := 1; i < len(fruits); i++ {
		if fruits[i] != fruit1 { //不是水果1，不能放1号篮子
			if fruit2 == -1 { //代表篮子2还空着
				fruit2 = fruits[i]
				lastFruit2Index = i
			} else if fruit2 == fruits[i] { //检查2号篮子的水果种类是不是fruits[i]
				lastFruit2Index = i
			} else {
				// 检查
				if maxNum < count {
					maxNum = count
				}
				// 需要清空一个篮子
				if lastFruit1Index >= lastFruit2Index { //清空2号篮子
					count = i - lastFruit2Index - 1
				} else {
					//清空1号篮子，将二号篮子水果放到一号篮子上
					count = i - lastFruit1Index - 1
					fruit1 = fruit2
					lastFruit1Index = lastFruit2Index
				}
				fruit2 = fruits[i]
				lastFruit2Index = i
			}
		} else { //是水果1
			lastFruit1Index = i
		}
		count++
	}
	if count > maxNum {
		maxNum = count
	}
	return maxNum
}

4.2 最小覆盖子串（76）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

解题思路：滑动窗口

func minWindow(s string, t string) string {
	t_arr := []rune(t)
	dict := make(map[rune]int)
	count := len(t_arr)
	for i := 0; i < count; i++ {
		dict[t_arr[i]]++
	}
	res := ""
	s_arr := []rune(s)
	left, right := 0, 0
	for right = 0; right < len(s_arr); right++ {
		value, exist := dict[s_arr[right]]
		if !exist {
			continue
		}
		dict[s_arr[right]] = value - 1
		if value > 0 {
			count--
		}
		if count == 0 { //当count==0表明此时刚好覆盖一个子串
			if res == "" || len(res) > right-left {
				res = string(s_arr[left : right+1])
			}
			//尝试进行left收缩直到不满足条件
			for j := left; j <= right; j++ {
				left++
				value, exist = dict[s_arr[j]]
				if exist {
					dict[s_arr[j]] = value + 1
					if value == 0 {
						count++
						if len(res) > right-left+1 && left-1 > 0 {
							res = string(s_arr[left-1 : right+1])
						}
						//不满足子串，结束收缩
						break
					}

				}
			}
		}
	}
	return res
}

5. 螺旋矩阵II（59）

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

func generateMatrix(n int) [][]int {
	matrix := make([][]int, 0)
	for i := 0; i < n; i++ {
		matrix = append(matrix, make([]int, n))
	}
	left, up, right, bottom := 0, 0, n-1, n-1
	count := 1
	for left <= right && up <= bottom {
		for i := left; i <= right; i++ {
			matrix[up][i] = count
			count++
		}
		up++
		for i := up; i <= bottom; i++ {
			matrix[i][right] = count
			count++
		}
		right--
		for i := right; i >= left; i-- {
			matrix[bottom][i] = count
			count++
		}
		bottom--
		for i := bottom; i >= up; i-- {
			matrix[i][left] = count
			count++
		}
		left++
	}
	return matrix
}

5.1 螺旋矩阵（54）

func spiralOrder(matrix [][]int) []int {
	left, up, right, bottom := 0, 0, len(matrix[0])-1, len(matrix)-1
	res := make([]int, len(matrix[0])*len(matrix))
	count := 0
	for left <= right && up <= bottom {
		for i := left; i <= right; i++ {
			res[count] = matrix[up][i]
			count++
		}
		up++
		if left > right || up > bottom {
			return res
		}
		for i := up; i <= bottom; i++ {
			res[count] = matrix[i][right]
			count++
		}
		right--
		if left > right || up > bottom {
			return res
		}
		for i := right; i >= left; i-- {
			res[count] = matrix[bottom][i]
			count++
		}
		bottom--
		if left > right || up > bottom {
			return res
		}
		for i := bottom; i >= up; i-- {
			res[count] = matrix[i][left]
			count++
		}
		left++
		if left > right || up > bottom {
			return res
		}
	}
	return res
}

5.2 剑指Offer-顺时针打印矩阵（29）

给的测试用例中有一个不是二维数组的空数组，需要特殊情况处理一下。

func spiralArray(matrix [][]int) []int {
    if len(matrix)==0{
        return make([]int,0)
    }
    left, up, right, bottom := 0, 0, len(matrix[0])-1, len(matrix)-1
	res := make([]int, len(matrix[0])*len(matrix))
	count := 0
	for left <= right && up <= bottom {
		for i := left; i <= right; i++ {
			res[count] = matrix[up][i]
			count++
		}
		up++
		if left > right || up > bottom {
			return res
		}
		for i := up; i <= bottom; i++ {
			res[count] = matrix[i][right]
			count++
		}
		right--
		if left > right || up > bottom {
			return res
		}
		for i := right; i >= left; i-- {
			res[count] = matrix[bottom][i]
			count++
		}
		bottom--
		if left > right || up > bottom {
			return res
		}
		for i := bottom; i >= up; i-- {
			res[count] = matrix[i][left]
			count++
		}
		left++
		if left > right || up > bottom {
			return res
		}
	}
	return res
}

6. 区间和

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
原题：区间和

6.1 基础版本（超时）

package main
import (
    "fmt"
)
func main() {
    var n int
    // 读取数组的长度
    fmt.Scan(&n)
    // 读取数组的元素
    array := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&array[i])
    }
    // 读取区间下标并计算总和
    for {
        var a, b int
        _, err := fmt.Scan(&a, &b)
        if err != nil {
            break
        }
        // 计算区间 [a, b] 的总和
        sum := 0
        for i := a; i <= b; i++ {
            sum += array[i]
        }
        // 输出总和
        fmt.Printf("%d\n", sum)
    }
}

6.2 改进版本（没通过）

这个版本没通过的原因是因为输入输出的原因，方法没问题

package main
import (
	"fmt"
)
func main() {
	var n int
	// 读取数组的长度
	fmt.Scan(&n)
	// 读取数组的元素
	array := make([]int, n)
	sum := make([]int, n+1)
	for i := 0; i < n; i++ {
		fmt.Scan(&array[i])
		sum[i+1] = sum[i] + array[i]
	}
	//fmt.Println(sum)
	//读取区间下标并计算总和
	for {
		var a, b int
		_, err := fmt.Scan(&a, &b)
		if err != nil {
			break
		}
		// 输出总和
		fmt.Printf("%d\n", sum[b+1]-sum[a])
	}
}

6.3 改进版本（改进输入输出）

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	// 读取数组的长度
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())

	// 读取数组的元素
	array := make([]int64, n)
	sum := make([]int64, n+1)
	for i := 0; i < n; i++ {
		scanner.Scan()
		array[i], _ = strconv.ParseInt(scanner.Text(), 10, 64)
		sum[i+1] = sum[i] + array[i]
	}

	// 读取区间下标并计算总和
	for scanner.Scan() {
		indices := strings.Fields(scanner.Text())
		if len(indices) < 2 {
			break
		}
		a, _ := strconv.Atoi(indices[0])
		b, _ := strconv.Atoi(indices[1])
		// 确保 a 和 b 在有效范围内
		if a < 0 || b < 0 || a >= n || b >= n || a > b {
			fmt.Println("Invalid range")
			continue
		}
		// 输出总和
		fmt.Printf("%d\n", sum[b+1]-sum[a])
	}
}

7. 开发商购买土地

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。 现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分

思路：基于前序和后序和

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	// 读取数组的长度
	scanner.Scan()
	indices := strings.Fields(scanner.Text())
	n, _ := strconv.Atoi(indices[0])
	m, _ := strconv.Atoi(indices[1])
	// 纵向求和和横向求和
	arr_x := make([]int, n)
	arr_y := make([]int, m)
	// 读取数组的元素
	matrix := make([][]int, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		row := strings.Fields(scanner.Text())
		matrix[i] = make([]int, m)
		sum := 0
		for j := 0; j < m; j++ {
			matrix[i][j], _ = strconv.Atoi(row[j])
			sum += matrix[i][j]
		}
		arr_x[i] = sum
	}
	for i := 0; i < m; i++ {
		sum := 0
		for j := 0; j < n; j++ {
			sum += matrix[j][i]
		}
		arr_y[i] = sum
	}
	// 前序和后续之和
	x_front, x_back := make([]int, m), make([]int, m)
	y_front, y_back := make([]int, n), make([]int, n)
	for i := 0; i < m; i++ {
		if i == 0 {
			x_front[0] = arr_y[0]
			x_back[m-1] = arr_y[m-1]
		} else {
			x_front[i] += x_front[i-1] + arr_y[i]
			x_back[m-1-i] = x_back[m-i] + arr_y[m-1-i]
		}
	}
	for i := 0; i < n; i++ {
		if i == 0 {
			y_front[0] = arr_x[0]
			y_back[n-1] = arr_x[n-1]
		} else {
			y_front[i] += y_front[i-1] + arr_x[i]
			y_back[n-1-i] = y_back[n-i] + arr_x[n-1-i]
		}
	}
	minGap := math.MaxInt32
	for i := 0; i < m-1; i++ {
		temp := x_front[i] - x_back[i+1]
		if temp < 0 {
			temp *= -1
		}
		if temp < minGap {
			minGap = temp
		}
	}
	for i := 0; i < n-1; i++ {
		temp := y_front[i] - y_back[i+1]
		if temp < 0 {
			temp *= -1
		}
		if temp < minGap {
			minGap = temp
		}
	}
	fmt.Println(minGap)
}