文章链接：代码随想录
记忆：
数组是存放在连续内存空间上的相同类型数据的集合。
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
- 数组的元素是不能删的，只能覆盖。
- 在C++中二维数组是连续分布的。
像Java是没有指针的，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机。二维数组的每一行头结点的地址是没有规则的，更谈不上连续。
所以Java的二维数组可能是如下排列的方式：
题目建议： 大家能把 704 掌握就可以，35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 ，如果有时间就去看一下，没时间可以先不看，二刷的时候在看。
先把 704写熟练，要熟悉 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法。
题目链接：
文章讲解：代码随想录
记忆：
第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
public int search(int[] nums, int target) { int i =0; int j= nums.length-1; while(i<=j){//左闭右闭，会有相遇的情况 int mid = j+(i-j)/2;//防溢出 if(nums[mid]<target){ i = mid+1;//已经确定不会等于mid } if(nums[mid]>target){ j = mid-1;//已经确定不会等于mid } if(nums[mid]==target){ return mid; } } return -1; } 时间复杂度：O(log n) 空间复杂度：O(1)
文章讲解：35.搜索插入位置
- 力扣题目链接
public int searchInsert(int[] nums, int target) { int i =0; int j= nums.length-1; while(i<=j){ int mid = i+(j-i)/2; if(nums[mid]<target){ i = mid+1; } if(nums[mid]>target){ j = mid-1; } if(nums[mid]==target){ return mid; } } return i;//或者j+1 } // 分别处理如下四种情况 // 目标值在数组所有元素之前 [0, -1] // 目标值等于数组中某一个元素 return middle; // 目标值插入数组中的位置 [left, right]，return right + 1 // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1 时间复杂度：O(log n) 空间复杂度：O(1)
public int[] searchRange(int[] nums, int target) { int i =0; int j= nums.length-1; while(i<=j){ int mid = j+(i-j)/2; if(nums[mid]<target){ i = mid+1; } if(nums[mid]>target){ j = mid-1; } if(nums[mid]==target){ int l=mid,r=mid;//从中间向两边扩展 while( l-1 >= 0 && nums[l--]==target ){//数组限制，防止溢出 if(nums[l]!=target){ l++; break; } } while(r+1 <= nums.length-1 && nums[r++]==target){ if(nums[r]!=target){ r--; break; } } return new int[]{l,r};//数组创建方式 } } return new int[]{-1,-1}; } 时间复杂度：O(log n) 空间复杂度：O(1)
public int mySqrt(int x) { if(x==0 || x==1){ return x; } int i =1; int j= x/2;//由于题目的特殊性可以这样设置 while(i<j){//左闭右开 int mid = i+(j-i+1)/2;//偏右 if(mid > x/mid){ j = mid-1; }else if(mid < x/mid){//由于题目的特殊性可以这样设置 i = mid; }else{ return mid; } } return i; } 时间复杂度：O(log n) 空间复杂度：O(1)
public boolean isPerfectSquare(int num) { if( num==1){ return true; } int i =0; int j= num; while(i<=j){ int mid = i+(j-i)/2; if(mid > num/mid){ j = mid-1; }else if(mid < num/mid){ i = mid+1; }else{ return true; } } return false; } 时间复杂度：O(log n) 空间复杂度：O(1) //完全二分法
题目建议： 暴力的解法，可以锻炼一下我们的代码实现能力，建议先把暴力写法写一遍。 双指针法 是本题的精髓，今日需要掌握，至于拓展题目可以先不看。
题目链接：力扣
文章讲解：代码随想录
视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili
public int removeElement(int[] nums, int val) { int slowIndex = 0; for(int fastIndex =0;fastIndex < nums.length; fastIndex++ ){ if(val != nums[fastIndex]){ nums[slowIndex++] = nums[fastIndex]; } } return slowIndex; 时间复杂度：O(n) 空间复杂度：O(1)
26.删除排序数组中的重复项
public int removeDuplicates(int[] nums) { int n = nums.length; int j = 0; for (int i = 0; i < n; i++) { if (nums[i] != nums[j]) { nums[++j] = nums[i]; } } return j+1; } 时间复杂度：O(n) 空间复杂度：O(1)
public void moveZeroes(int[] nums) { int slowIndex = 0; for(int fastIndex = 0; fastIndex<nums.length;fastIndex++){ if(nums[fastIndex]!= 0){ nums[slowIndex++]=nums[fastIndex]; } } for(int i = slowIndex; i<nums.length;i++){ nums[i]=0; } } 时间复杂度：O(n) 空间复杂度：O(1)
public boolean backspaceCompare(String s, String t) { return convert(s).equals(convert(t)); } private String convert(String s1) { StringBuilder s = new StringBuilder(); char[] sc = s1.toCharArray(); int j=0; for(int i =sc.length-1; i>=0 ;i-- ){ if(sc[i]=='#'){ j++; }else if(j==0){ s.append(sc[i]); }else if(sc[i]!='#'){ j--; } } return s.toString(); } 时间复杂度：O(n) 空间复杂度：O(1)
977.有序数组的平方
public int[] sortedSquares(int[] nums) { int[] newnums = new int[nums.length]; for(int i=0,j=nums.length-1,k=nums.length-1;i<=j; k--){ int m = nums[i]*nums[i]; int n = nums[j]*nums[j]; if(m>n){ newnums[k] = m; i++; }else{ newnums[k] = n; j--; } } return newnums; } //时间复杂度为O(n)
