数组专题总结
数组在内存中的存储方式，是在连续内存空间上的相同类型数据的集合，可以方便通过下标索引的方式来获取到下标下对应的数据。
需要注意的是：数组下标是从0开始，数组内存空间的地址是连续的，因为数组的内存空间的地址是连续的，所以我们在删除或者添加元素的时候，就难免要移动其他元素的地址。
如果要删除一个数组里的某个数，那么该元素后的所有元素都要做移动的操作，所以数组的元素是不能够删除的，只能够覆盖。
java中一维数组内存是连续的，但是二维数组不是连续的，二维数组的内存空间是由四条连续的地址空间组成。
二分法专练
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
经典的二分模板类型题，对于已经排序好的数组，要找某一个数，直接要想到可以使用二分法来进行解决。时间复杂度O(logn)
java参考代码：
class Solution { public int search(int[] nums, int target) { if(target<nums[0] || target>nums[nums.length-1]){ return -1; } int left = 0,right =nums.length-1; while(left<=right){ int mid = left +((right-left)>>1); if(nums[mid] == target){ return mid; } if(nums[mid]>target){ right =mid-1; } if(nums[mid]<target){ left = mid+1; } } return -1; } }
go参考代码：
func search(nums []int, target int) int { if target<nums[0] || target>nums[len(nums)-1]{ return -1; } left,right := 0,len(nums)-1 for left<=right{ mid := left+((right-left)>>1) if nums[mid] == target{ return mid } if nums[mid]<target{ left =mid+1 } if nums[mid]>target{ right =mid-1 } } return -1 }
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
这道题要求使用O(logn)，同时也是排序后的数组，所以可以使用二分法来进行排序
java参考代码：
class Solution { public int searchInsert(int[] nums, int target) { int left=0,right=nums.length-1; while(left<=right){ int mid = left+((right-left)>>1); if(nums[mid] == target){ return mid; }else if(nums[mid]<target){ left=mid+1; }else{ right = mid-1; } } return left; } }
go参考代码：
func searchInsert(nums []int, target int) int { left,right :=0,len(nums)-1 for left<= right{ mid:=left+((right-left)>>1) if nums[mid] == target { return mid } if nums[mid] > target { right = mid-1 } if nums[mid] < target { left = mid+1 } } return left }
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
题中对时间复杂度进行了要求，同时题中要求了数组为非递减，所以可以使用二分法。但是这道题返回的是一个范围，我们知道，二分法每次只能确定一个值，所以我们可以通过两次二分，来分别获得左边界和右边界的值，最后返回一个区间。
本文之前有过讲解，具体思路和流程参考这里：Leetcode34思路解读
java参考代码：
class Solution { public int[] searchRange(int[] nums, int target) { int left = searchLeft(nums,target); int right= searchright(nums,target); if(left == -1 || right == -1){ return new int[]{-1,-1}; }else{ return new int[]{left,right}; } } //寻找目标值左边界m public int searchLeft(int[]nums,int target){ int left=0,right=nums.length-1; while(left<=right){ int mid =left+((right-left)>>1); if(nums[mid] == target){ if(mid == 0 || nums[mid-1]<target){ return mid; } right =mid-1; } if(nums[mid]>target){ right = mid-1; } if(nums[mid]<target){ left = mid+1; } } return -1; } public int searchright(int []nums,int target){ int left = 0,right=nums.length-1; while(left<=right){ int mid = left+((right-left)>>1); if(nums[mid] == target){ if(mid == nums.length-1 || nums[mid+1]>target){ return mid; } left = mid+1; } if(nums[mid]>target){ right=mid-1; } if(nums[mid]<target){ left = mid+1; } } return -1; } }
go参考代码：
func searchRange(nums []int, target int) []int { left := searchleft(nums,target) right := searchright(nums,target) if left== -1 || right == -1{ return []int{-1,-1} }else{ return []int{left,right} } } func searchleft(nums [] int,target int) int{ left,right:=0,len(nums)-1 for left<=right{ mid := left+((right-left)>>1) if nums[mid] == target{ if mid == 0 || nums[mid-1]<target{ return mid } right = mid-1 } if nums[mid]<target{ left =mid+1 } if nums[mid]>target{ right = mid-1 } } return -1 } func searchright(nums [] int,target int) int{ left,right:=0,len(nums)-1 for left<=right{ mid := left+((right-left)>>1) if nums[mid] == target{ if mid == len(nums)-1 || nums[mid+1]>target{ return mid } left = mid+1 } if nums[mid]<target{ left =mid+1 } if nums[mid]>target{ right = mid-1 } } return -1 }
通过上面两道题的解题思路，你应该能有很多收获，下面这里两道题就当做课后练习吧，不会的话可以回顾前面题解思路，尝试自己去把做出来
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。
双指针专练
双指针法：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
本题主要考点是双指针中的快慢指针的应用，相信通过1,2,3题，你会有很多收获。本题之前有过讲解：可以参考该文献：移除元素思路讲解
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
本题的话，也是双指针的一个应用，快慢指针，本文之前有过讲解:可供参考思路：删除有效数组的重复项思路讲解
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
本题同样是双指针中快慢指针的练习，你可以尝试不看题解，自己做出来，就当做前两道题的练习题，考验一下自己的知识的了解程度
本文之前有过讲解：可以参考文章思路：移动零思路讲解
- 比较含退格的字符串
这道题可以使用栈和双指针进行解答，难度感觉还是不简单，可以参考我之前文章思路：比较含退格的字符串思路讲解
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true
。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
- 有序数组的平方
本题同样可以使用双指针解题，分为首尾双指针法，不是前几道题的快慢双指针，题解思路可以参考之前的文献：有序数组的平方思路讲解
滑动窗口专练
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
可以先思考，没有思路和头绪的话可以参考我之前的文章：长度最小的子数组思路解读
下面给出两道类似的滑动窗口练习题：做题首先想思路，没有思路的话可以参考题解
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
模拟行为专练
题目描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
可以先思考，同时可以参考我之前文献思路：螺旋数组思路解读
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
可以先思考，同时可以参考我之前的文献：螺旋数组II思路解读
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
go参考代码：
func spiralOrder(matrix [][]int) []int { if(len(matrix) == 0){ return []int{} } top,left,right,bottom :=0,0,len(matrix[0])-1,len(matrix)-1 res :=[]int{} for left<=right && top <=bottom{ for i:=left;i<=right;i++{res=append(res,matrix[top][i])} top++ if top>bottom{ return res } for i:=top;i<=bottom;i++{res=append(res,matrix[i][right])} right-- if right<left{ return res } for i:=right;i>=left;i--{res=append(res,matrix[bottom][i])} bottom-- if bottom<top{ return res } for i:=bottom;i>=top;i--{res=append(res,matrix[i][left])} left++ if left>right{ return res } } return res }
希望对您的算法学习能有所帮助，您的支持是我前进的最大动力，感谢您的关注和认可！！！
