꒰˃͈꒵˂͈꒱ write in front꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ原创 CSDN如需转载还请通知˶⍤⃝˶
个人主页：xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏：xiaoxie的刷题系列专栏——CSDN博客●’ᴗ’σσணღ*
我的目标:”团团等我( ◡̀_◡́ ҂)”

(⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞 + 收藏⭐️ + 留言​+关注（互三必回）!

数组篇

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

力扣链接

我相信大家一看到这题是有序的数组，有点基础的同学们都会想到二分查找法，这一题有思路很容易，但提交时却老是无法通过，这就是因为没有考虑好边界问题了，现在博主为大家介绍两种二分查找法

1.普通二分查找法

做好这一题的关键就在于找到边界

题就是查找 target 在 nums 中的区间，即查找 target 在 nums 中的左右边界。

仔细想的话，要找 target 在 nums 数组中的左右边界，无非存在 3 种情况：

target 在 nums[0] ~ nums[n-1] 中，nums 中存在 target。例如 nums = [5,7,7,8,8,10]，target = 8，返回 [3，4]。
target 在 nums[0] ~ nums[n-1] 中，nums 中不存在 target。例如 nums = [5,7,7,8,8,10]，target = 6，返回 [-1,-1]。
target nums[n-1]。例如 nums = [5,7,7,8,8,10], target = 4，返回 [-1,-1]。

用两个二分查找，一个二分查找查找左边界，另一个查找右边界，分情况讨论上述的 3 种情况。

class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums, target);if (start == nums.length || nums[start] != target)return new int[]{-1, -1};// 如果 start 存在，那么 end 必定存在int end = lowerBound(nums, target + 1) - 1;return new int[]{start, end};}private int lowerBound(int[] nums, int target) {int left = 0, right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1; // 范围缩小到 [mid+1, right]elseright = mid - 1; // 范围缩小到 [left, mid-1]}return left; // right+1}

2.红蓝二分查找法

相信大家一直对二分查找法的边界问题一直有困扰，一般来说二分查找就这些东西，在边界和细节上搞人，只要每次做题小心点，就没啥问题。现在博主就为大家介绍另外一种二分查找方法，它不需要考虑那么多问题，只要在最后返回值时多多注意就好了

class Solution {public int searchRangeLeft(int[] nums, int target) {int left = -1;int right = nums.length;while (left + 1 != right) {int mid = (left + right) / 2;if (nums[mid] <= target) {left = mid;} else {right = mid;}}return left;}public int searchRangeRight(int[] nums, int target) {int left = -1;int right = nums.length;while (left + 1 != right) {int mid = (left + right) / 2;if (nums[mid] = rightIndex && leftIndex < nums.length && nums[leftIndex] == target && nums[rightIndex] == target) {return new int[] {rightIndex, leftIndex};}return new int[] {-1, -1};}}

开始时，L指针和 R指针取在搜索区间界外，L=首个元素下标−1，R=末尾元素下标+1，此时所有元素均未着色；
循环条件始终为 L+1 < R，当 L=R时跳出循环，此时蓝红区域划分完成，所有元素均已着色；
M指针取值始终为 M =(L+R)/2
L指针和 R指针变化的时候直接变为 M指针，即对 M 指针所指向元素进行染色，无需 +1或者−1；
本模板唯一变化的地方是判断目标元素最终落在左边蓝色区域还是右边红色区域。以不变应万变，根据情况的不同，变换判断条件，大大的降低了出错的可能。

这样就找到左下标和右下标啦，再因为该题是找不到就返回-1，所以还要再判断，同时红蓝二分查找法并不只是适用于这题哦，它在大部分的题目都适用，目前博主还没有遇到不适用的情况，所以大家可以放心用，在变换判断条件时和普通二分查找法，大大的降低了出错的可能。

2.删除有序数组中的重复项—快慢指针

这是力扣上的一道简单题，有的同学可能说了，多余的元素，删掉不就得了。

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖，所以从中我们第一时间想到也是最简单的就是暴力解法

1.暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

public int removeDuplicates(int[] nums) {if (nums.length == 0) {return 0;}int k = 1; // 记录唯一元素的个数for (int i = 1; i < nums.length; i++) {boolean isDuplicate = false;// 检查当前元素是否已经存在于前面的唯一元素中for (int j = 0; j < k; j++) {if (nums[i] == nums[j]) {isDuplicate = true;break;}}// 如果当前元素是新的唯一元素，则加入到唯一元素列表中if (!isDuplicate) {nums[k] = nums[i];k++;}}return k;}

很明显暴力解法的时间复杂度是O(n^2)，这道题目暴力解法在leetcode上是可以过的。但这面试中你写这个解法，显然是不能让面试官满意的。博主这有一个使用双指针，快慢指针的解法

2.快慢指针

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

定义快慢指针

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

很多同学这道题目做的很懵，就是不理解 快慢指针究竟都是什么含义，所以一定要明确含义，后面的思路就更容易理解了。要解这题的思路如下

首先我们写记录下数组第一个元素的数值：

 int val = nums[0];

然后我们在定义一个快指针和慢指针，指向数组第二个元素：然后快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组；慢指针：指向更新 新数组下标的位置，如下图：

public int removeDuplicates(int[] nums) {int val = nums[0]; // 记录当前唯一元素的值int slow = 1; // 慢指针，指向下一个唯一元素应该存放的位置for (int fast = 1; fast < nums.length; fast++) {if (nums[fast] != val) { // 如果当前元素与前一个唯一元素不相同nums[slow] = nums[fast]; // 将当前元素存放到慢指针指向的位置val = nums[slow]; // 更新当前唯一元素的值slow++; // 慢指针向后移动}}return slow; // 返回唯一元素的个数}

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法，写成这样你的代码才可以说达到了面试的高度了，所以我们遇到这一类的题型可以多往快慢指针法那边靠靠，我相信你多练习，多学习，一定可以做到更好。

3.长度最小的子数组

这是力扣上的一道中等难度的数组题，还是一样看到这一题，第一个想到的方法就是用两个for 循环的暴力解法

1.暴力解法

public class Solution {public int minSubArrayLen(int s, int[] nums) {int result = Integer.MAX_VALUE; // 最终的结果int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度for (int i = 0; i < nums.length; i++) { // 设置子序列起点为isum = 0;for (int j = i; j = s) { // 一旦发现子序列和超过了s，更新resultsubLength = j - i + 1; // 取子序列的长度result = result 
 
 
代码如下：
 
class Solution {public int minSubArrayLen(int target, int[] nums) {int result = Integer.MAX_VALUE;int star = 0,end = 0; int sum = 0;for(;end = target) {int subl = end - star+1;result = Math.min(subl,result);//动态更新数值sum -= nums[star++];} }return result == Integer.MAX_VALUE ? 0 : result;}}
好了这就是数组篇的全部内容了，后续博主还会持续更新，链表篇等等内容，大家可以点个关注，不错过后续精彩内容。感谢您的阅读，祝您一天生活愉快