class Solution {public int search(int[] nums, int target) {return twoPart(nums,target,0,nums.length-1);}private int twoPart(int[] nums, int target, int start, int end){if(start>end) return -1;if(target==nums[(end-start)/2+start]){return (end-start)/2+start;} else if(targetreturn twoPart(nums,target,start,(end-start)/2+start-1);}else{return twoPart(nums,target,(end-start)/2+start+1,end);}}
}

class Solution {public int search(int[] nums, int target) {return twoPart(nums,target,0,nums.length);}private int twoPart(int[] nums, int target, int start, int end){if(start>=end) return -1;if(target==nums[(end-start)/2+start]){return (end-start)/2+start;} else if(targetreturn twoPart(nums,target,start,(end-start)/2+start);}else{return twoPart(nums,target,(end-start)/2+start+1,end);}}
}

二分查找相关题目 - 35. 搜索插入位置

35. 搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5
输出: 2示例 2:
输入: [1,3,5,6], 2
输出: 1示例 3:
输入: [1,3,5,6], 7
输出: 4示例 4:
输入: [1,3,5,6], 0
输出: 0

提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

解题思路

本题中数组为升序无重复的数组，所以想到用二分搜索法提高效率。和704的差别只在于找不到时要返回插入的位置。

解题方法

注意插入的位置不是索引而是第几个，所以返回right即可。

class Solution {public int searchInsert(int[] nums, int target) {int left=0;int right=nums.length;while(leftint mid=(right-left)/2+left;if(nums[mid]==target){return mid;}else if(target>nums[mid]){left=mid+1;}else{right=mid;}}return right;}
}

二分查找相关题目 - 34. 在排序数组中查找元素的第一个和最后一个位置

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

题目描述

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

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

解题思路

这道题目与之前的区别在于元素可以重复，并其需要返回开始和结束的两个值。

寻找target在数组里的左右边界，有如下三种情况：- 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4,5},target为6，此时应该返回{-1, -1} - 情况二：target在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1} - 情况三：target在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

解题方法

class Solution {int[] searchRange(int[] nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};// 情况三if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};// 情况二return new int[]{-1, -1};}int getRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
}

移除元素

27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

解题思路1

我们知道数组不能直接删除只能覆盖其他值，所以当找到相等的元素要让后面的覆盖前面的。
因为相等的可能有多个元素，所以需要一个计数器，以便之后的元素知道向前覆盖几个元素。

解题方法1

class Solution {public int removeElement(int[] nums, int val) {int n=0;for(int i=0;inums[i]=nums[i+n];if(nums[i+n]==val){--i;++n;}}return nums.length-n;}
}

解题思路2

双指针法
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

解题方法2

class Solution {public int removeElement(int[] nums, int val) {int slow=0;for(int fast=0;fastif(nums[fast]!=val){nums[slow++] = nums[fast];}}return slow;}
}

有序数组的平方

977. 有序数组的平方

题目描述

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

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题

解题思路

暴力解法肯定就是先平方后排序，但是这样时间复杂度最少也需要O(n + nlogn)。
时间为O(n)的方法肯定是只需要遍历一遍数组，最大值一定在数组的左右两端，定义两个指针分别从两端遍历再加到结果数组中。

解题方法

class Solution {public int[] sortedSquares(int[] nums) {int[] res=new int[nums.length];int i=0;int j=nums.length-1;int k=nums.length-1;while(i<=j){if(nums[i]*nums[i]>nums[j]*nums[j]){res[k--]=nums[i]*nums[i];i++;}else{res[k--]=nums[j]*nums[j];j--;}}return res;}
}

长度最小的子数组

209.长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
输入：target = 4, nums = [1,4,4]
输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：
请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题思路

双循环显然是时间复杂度是n²。
滑动窗口思想：不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
定义两个指针left、right，一个快一个慢，计算指针之间的值sum，并记录窗口的size；
若是>=target，right则向后移动，并且同时sum应减去i位置的值，注意这里是while循环，不一定只减去1个才

解题方法

class Solution {public int minSubArrayLen(int target, int[] nums) {int left=0;int sum=0;int result=nums.length+1;for(int right=0;rightsum+=nums[right];while(sum>=target){int min=right-left+1;if(minresult=min;}sum-=nums[left];++left;}}if(result==nums.length+1) return 0;return result;}
}

长度最小的子数组相关题目 - 904. 水果成篮

904. 水果成篮

题目描述

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

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

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

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：
1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length

解题思路

既然是相关题目，那么它和长度最小的子数组的相关性在哪里呢？
收集水果只有两个篮子，也就是只有两个种类的水果可以收集，且连续，所以滑动窗口中包含两个种类，数量是右边界-左边界+1。
那么left的变换规则是什么呢？
定义一个change，表示当前right的上一个不同种类水果的起始位置，也就是change的上一个也一定不相同，right如果和上一个&&上上一个不同，left则需更新到上一个的起始位置。
只要right和change不同，就需要更新change。

解题方法

class Solution {public int totalFruit(int[] fruits) {if(fruits.length<3) return fruits.length;int left=0;int change=0;int result=1;for(int right=1;right//change就是right的前一个，如果right为第三种水果则需要更新leftif(change-1>=0&&fruits[right]!=fruits[change-1]&&fruits[right]!=fruits[change]){left=change;}//只要right和change不同，就需要更新change。if(fruits[right]!=fruits[change]){change=right;}if(right-left+1>result) result=right-left+1;}return result;}
}

另外一个是官方解法，用HashMap保存采摘的水果，如果超过2个，则需要将key最左边种类的水果全部清除并更新left。

class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;//建立哈希表 int int类型Map cnt = new HashMap();int left = 0, ans = 0;for (int right = 0; right < n; ++right) {//getOrDefault() 获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值//left和right分别表示子数组（窗口）的左右边界，同时利用哈希表来存储这个窗口内的数以及**出现的次数**。cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);//key是存储在窗口内的数，value是出现的次数while (cnt.size() > 2) {//如果哈希表大小大于2，那就移动left将fruits[left]从哈希表中移除，直到满足要求为止。cnt.put(fruits[left], cnt.get(fruits[left]) - 1);//将（最左number，最左index）键/值对添加到 hashMap 中//如果fruits[left]在哈希表中出现的次数减少为0，那么要将其key值移出，此时哈希表大小=2，继续循环。if (cnt.get(fruits[left]) == 0) {//key值等于0 相当于left挪动index+1次cnt.remove(fruits[left]);}left++;}ans = Math.max(ans, right - left + 1);}return ans;}
}

长度最小的子数组相关题目 - 76. 最小覆盖子串

76. 最小覆盖子串

题目描述

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

注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

解题思路

依然是滑动窗口的思想，窗口内是s的子串。

• 如果子串包含t，则left向右移动。
• 如果子串不包含t所有字符，则right向右移动。

如何判断t中的字符是否包含在s中也是一个难点，t中字符可以重复，t的顺序不重要。
使用sum表示s子串中包含t的字符的个数，超过个数就不再增加。

解题方法

以下为官方解法。

class Solution {public String minWindow(String s, String t) {//将s和t转换为字符数组char[] chs1 = s.toCharArray();char[] chs2 = t.toCharArray();//cnt是固定的，记录t中各个字符的频次，直接以字符的asc码为下标int[] cnt = new int[128];for(char ch : chs2) {cnt[ch]++;}//sum计数，如果t中所有元素都存在在s中则－为0int sum = chs2.length;int left = 0, right = 0; //[left, right)//记录长度最小时的下标int p1 = -1, p2 = -1;while(left < chs1.length && right < chs1.length) {//如果t中的字符在s中存在，也就是以right为下标的s中的字符在cnt数组中为下标时元素大于0//子串还没有完全包含t，right++if(cnt[chs1[right++]]-- > 0) {sum--;}   //子串包含t，left要向右移动while(sum == 0) {//计算是否为最小长度if(p1 == -1 || right-left < p2-p1) {p1 = left;p2 = right;}if(cnt[chs1[left++]]++ >= 0)sum++;} }return p1==-1 ? "" : s.substring(p1, p2);}
}

59. 螺旋矩阵 II

59. 螺旋矩阵 II

题目描述

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

示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]示例 2：
输入：n = 1
输出：[[1]]

提示：
1 <= n <= 20

解题思路

螺旋的过程：行从左到右，列从上到下，行从右到左，列从下到上，不断循环往复的过程

解题方法

模拟螺旋的过程，边界条件左闭右开

class Solution {public int[][] generateMatrix(int n) {int result[][]=new int[n][n];int sum,start,offset,i,j;start=0;//每次循环开始的位置sum=offset=1;//sum用来表示要填充的数字，每次＋1//offset用来控制循环的次数，表示要循环几圈while(offset<=n/2){//从左到右for(j=start;jresult[start][j]=sum++;}//从上到下for(i=start;iresult[i][j]=sum++;}//从右到左for(;j>=offset;j--){result[i][j]=sum++;}//从下到上for(;i>=offset;i--){result[i][j]=sum++;}offset++;start++;}//中间点if (n % 2 == 1) {result[start][start] = sum;}return result;}
}

螺旋矩阵 II - 54. 螺旋矩阵

54. 螺旋矩阵

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

解题思路

上一题是知道填充数求矩阵，这一题是知道矩阵，求螺旋数组。
本题要考虑不一定是正方形矩阵的情况，所以循环的圈数为Math.min(m,n)/2 + Math.min(m,n)%2;
如果只有一行，list便会重复添加从右到左，所以最后result = result.subList(0,m*n);，只保留m×n个元素

解题方法

class Solution {public List spiralOrder(int[][] matrix) {List result=new ArrayList();int m = matrix.length;int n = matrix[0].length;//需要转的圈数int cycle = Math.min(m,n)/2 + Math.min(m,n)%2;int offset=1;int start,i,j;start=0;while(offset<=cycle){//从左到右for(j=start;jresult.add(matrix[start][j]);}//从上到下for(i=start;iresult.add(matrix[i][j]);}//从右到左for(;j>=offset;j--){result.add(matrix[i][j]);}//从下到上for(;i>=offset;i--){result.add(matrix[i][j]);}offset++;start++;}if (m%2 != 0 && n%2 != 0) {result.add(matrix[m/2][n/2]);}result = result.subList(0,m*n);return result;}
}