数组 from 代码随想录
二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
左闭右闭
func search(nums []int, target int) int {lf,rf := 0,len(nums) - 1for lf <= rf {middle := (lf + rf)/2if nums[middle] > target{rf = middle - 1}else if nums[middle] < target {lf = middle + 1}else{return middle}}return -1
}
左闭右开
func search(nums []int, target int) int {lf,rf := 0,len(nums)for lf < rf {middle := (lf + rf)/2if nums[middle] > target{rf = middle}else if nums[middle] < target {lf = middle + 1}else{return middle}}return -1
}
移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路:快慢双指针
func removeElement(nums []int, val int) int {res := 0for i,total:=0,len(nums); i<total;i++{if nums[i] != val {nums[res] = nums[i]res ++ }}nums = nums[:res]return res
}
有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
思路:因为是非递减数组,默认排序,所以用双指针(从首末开始),创建新数组,用指针从末尾开始写入
func sortedSquares(nums []int) []int {left,right,flag := 0,len(nums) - 1,len(nums) - 1newNums := make([]int,len(nums))for left <= right {if nums[left] * nums[left] < nums[right] * nums[right] {newNums[flag] = nums[right] * nums[right]right --}else{newNums[flag] = nums[left] * nums[left]left ++}flag --}return newNums
}
滑动窗口
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
思路:滑动窗口,本质上为双指针(start为慢指针,end为快指针),只是取的是双指针之间(包含两端)之间的内容,以和小于target驱动end指针,以和大于等于target驱动start指针。
func minSubArrayLen(target int, nums []int) int {n := len(nums)if n == 0 {return 0}start,end,sum := 0,0,0ans := math.MaxInt32for end < n {sum += nums[end]for sum >= target {ans = min(ans,end - start + 1)sum -= nums[start]start ++ }end ++ }if ans == math.MaxInt32 {return 0}return ans
}func min(x,y int)int{if x < y {return x}return y
}
螺旋矩阵II
给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
思路:先初始化一个矩阵,按顺序模拟顺时针处理,注意边界点处理
func generateMatrix(n int) [][]int {top, bottom, left, right := 0, n-1, 0, n-1num := 1tar := n * nmatrix := make([][]int, n)for i := 0; i < n; i++ {matrix[i] = make([]int, n)}for num <= tar {//上->右->下->左//上边for i := left; i <= right; i++ {matrix[top][i] = numnum++}top++//右边for i := top; i <= bottom; i++ {matrix[i][right] = numnum++}right--//下边for i := right; i >= left; i-- {matrix[bottom][i] = numnum++}bottom--//左边for i := bottom; i >= top; i-- {matrix[i][left] = numnum++}left++}return matrix
}