【代码随想录——数组—

数组

1. 二分查找(704)

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

1.1 二分法的第一种写法

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

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

递归写法

go">func search(nums []int, target int) int {l, r := 0, len(nums)-1return searchBinary(nums, target,l,r)
}func searchBinary(nums []int,target,left,right int) int {if left>right{return -1}mid := (left+right)/2if 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)
常规写法

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

递归写法

go">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)/2if 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）

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

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

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

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

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

go">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 + 1res[1] = right - 1return res
}func FindGIndex(nums []int,target int)int{low,high,mid := 0,len(nums)-1,0for low<=high{mid = low+(high-low)/2if 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,0for low<=high{mid = low+(high-low)/2if 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 。

go">func mySqrt(x int) int {return binarySearch(x)
}func binarySearch(target int) int{low,high,mid := 0,target,0for low<=high{mid = low+(high-low)/2pow_num := mid*midif 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 。

go">func isPerfectSquare(num int) bool {return binarySearch(num)
}func binarySearch(target int) bool{low,high,mid := 0,target,0for low<=high{mid = low+(high-low)/2pow_num := mid*midif 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 不同的元素的数量。
快慢指针

go">func removeElement(nums []int, val int) int {fastPoint,slowPoint := 0,0for 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 中唯一元素的个数。

go">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 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。

go">func moveZeroes(nums []int)  {zeroNum,currentIndex := 0,0for 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 。# 代表退格字符。

go">func backspaceCompare(s string, t string) bool {return paresStr(s)==paresStr(t)
}func paresStr(s string) string {r := []rune(s)currentIndex := 0for 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 不太雅观的代码

go">func sortedSquares(nums []int) []int {firstPositiveIndex := -1lengthOfNums := len(nums)for i := 0; i < lengthOfNums; i++ {if nums[i] > 0 {firstPositiveIndex = ibreak}}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 []intleft, 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 美观代码

go">func sortedSquares(nums []int) []int {firstPositiveIndex := -1lengthOfNums := len(nums)for i := 0; i < lengthOfNums; i++ {if nums[i] > 0 {firstPositiveIndex = ibreak}}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 []intarr1Index, arr2Index := 0, 0for 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 intfor start < end {temp = nums[start]nums[start] = nums[end]nums[end] = tempstart++end--}
}// [start,end]
func powOfArr(nums []int, start, end int) []int {var res []intfor i := start; i <= end; i++ {res = append(res, nums[i]*nums[i])}return res
}

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

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

go">// 查找大于等于 num 的第一个数的下标
func findFirstGeNumIndex(nums []int, num int) int {low, high := 0, len(nums)-1for low <= high {mid := low + (high-low)/2if nums[mid] >= num {//保证了nums[high]最终一定小于numhigh = 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)-1for low <= high {mid := low + (high-low)/2if nums[mid] > num {//保证了nums[high]最终一定小于等于numhigh = 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)-1for low <= high {mid := low + (high-low)/2if nums[mid] <= num {// 保证了nums[low]大于等于numlow = 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)-1for low <= high {mid := low + (high-low)/2if nums[mid] < num {// 保证了nums[low]大于numlow = 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 。

快慢指针法

go">func minSubArrayLen(target int, nums []int) int {slow, fast, sum := 0, 0, 0minLen := math.MaxInt32for _, num := range nums {sum += numfast++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个测试用例超时了

go">func totalFruit(fruits []int) int {maxNum := 0for 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],-1count := 1for 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 剪枝的双重循环

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

go">func totalFruit(fruits []int) int {maxNum := 0for 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],-1count := 1for 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 滑动窗口（正解）

go">func totalFruit(fruits []int) int {lastFruit1Index, lastFruit2Index, count := 0, -1, 1fruit1, fruit2 := fruits[0], -1maxNum := 0for 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 - 1fruit1 = fruit2lastFruit1Index = lastFruit2Index}fruit2 = fruits[i]lastFruit2Index = i}} else { //是水果1lastFruit1Index = i}count++}if count > maxNum {maxNum = count}return maxNum
}

4.2 最小覆盖子串（76）

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

解题思路：滑动窗口

go">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, 0for right = 0; right < len(s_arr); right++ {value, exist := dict[s_arr[right]]if !exist {continue}dict[s_arr[right]] = value - 1if 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 + 1if 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

go">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-1count := 1for left <= right && up <= bottom {for i := left; i <= right; i++ {matrix[up][i] = countcount++}up++for i := up; i <= bottom; i++ {matrix[i][right] = countcount++}right--for i := right; i >= left; i-- {matrix[bottom][i] = countcount++}bottom--for i := bottom; i >= up; i-- {matrix[i][left] = countcount++}left++}return matrix
}

5.1 螺旋矩阵（54）

go">func spiralOrder(matrix [][]int) []int {left, up, right, bottom := 0, 0, len(matrix[0])-1, len(matrix)-1res := make([]int, len(matrix[0])*len(matrix))count := 0for 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）

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

go">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)-1res := make([]int, len(matrix[0])*len(matrix))count := 0for 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 基础版本（超时）

go">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 := 0for i := a; i <= b; i++ {sum += array[i]}// 输出总和fmt.Printf("%d\n", sum)}
}

6.2 改进版本（没通过）

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

go">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 改进版本（改进输入输出）

go">package mainimport ("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 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分

思路：基于前序和后序和

go">package mainimport ("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 := 0for 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 := 0for 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.MaxInt32for 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)
}