【基础算法】数组相关题目

系列综述：
💞目的：本系列是个人整理为了秋招算法的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于代码随想录进行的，每个算法代码参考leetcode高赞回答和其他平台热门博客，其中也可能含有一些的个人思考。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈数据结构基础知识总结篇

---

---

😊点此到文末惊喜↩︎

---

二分查找

基本二分法

1. 二分法前提（有序无重复的数组）
   • 数组有序：一次比较即可确定需要查找的那一半，效率高的关键
   • 数组中无重复元素：一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一
   • 查找对象为数组：数组可以进随机存取
2. 边界处理方式
   • 左闭右闭 [left, right]：基本算法，可以定位后再寻找相同元素区域的左右边界
   • 左闭右开 [left, right)：可以在存在相同元素时，定位到相同元素区域的 左右边界
3. leetcode题目：704. 二分查找
   

   // *****************前闭后闭的基本二分查找，可以代替下一种*******************
   int search(vector<int>& nums, int target) {
   // 0. 健壮性检查if(nums.size() <= 0) return -1;
   // 1. 定义边界指针（指向遍历数组区域的边界位置）int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里
   // 2. 基本算法步骤的循环    while (left <= right) { // 前闭后闭用<=// - 定义int mid = left + ((right - left)>>2);// 防止溢出 等同于(left + right)/2// 目标值在左区间if (target < nums[mid]) {right = mid - 1; // 目标值在右区间} else if (target > nums[mid]) {left = mid + 1; // 找到目标值，即相等时} else {return mid; // 数组中找到目标值，直接返回下标}}
   // 3. 添加进行左右边界的定位操作// ...return -1;// 未找到目标值
   }
   

   • mid = L + ((R - L)>>1)
     • 防溢出：如果L 和 R太大，直接相加就有溢出的可能
     • 移位：等价于除法算法，但是效率高
   • 使用前闭后闭的二分区域查找，可以在查找target位置后再进行相同元素相连区域的定位操作。

---

搜索插入位置

1. 该题与二分查找类似，但是最后返回的是插入的位置，所以没找到时应该返回的是最后比较的位置的后一个
2. leetcode题目：35. 搜索插入位置
   

   class Solution {
   public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;while (left <= right){int mid = left + ((right-left) >> 2);if(target < nums[mid]){right = mid - 1;}else if(target > nums[mid]){left = mid + 1;}else{return mid;}}return left;// left为相等值未找到时应插入的位置}
   };
   

---

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

1. 该题与二分查找类似，但是最后应该对于相邻相同元素的起始和末尾进行遍历判断
2. leetcode题目：35. 搜索插入位置
   

   vector<int> searchRange(vector<int>& nums, int target) {vector<int> res(2,-1);// 初始化两个值为-1的元素if(nums.size() <= 0) return res; // 基本二分法int left = 0;int right = nums.size()-1;int mid;while(left <= right){mid = left + ((right -left) >> 2);if(target < nums[mid]){right = mid - 1;}else if(target > nums[mid]){left = mid + 1;}else{break;// 保留mid}}// 寻找相似相邻区间的左右边界int l = mid;int r = mid;if(nums[mid] != target){return res;}else{while (l > 0){if(nums[l] == nums[l-1]){l--;}elsebreak;}while (r < nums.size()-1){if(nums[r] == nums[r+1]){r++;}elsebreak;}}cout << res[0]<< endl;res[0]=l;res[1]=r;return res;}
   

---

快慢指针

移除元素

1. 快慢指针
   • 快指针fast用于条件判断
   • 慢指针slow用于位置保存
2. leetcode题目：27. 移除元素

   给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
   不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
   元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
   示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
   示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 你不需要考虑数组中超出新长度后面的元素。

   int removeElement(vector<int>& nums, int val) {// 快慢指针int slow = 0;int fast = slow;while(fast < nums.size()){if(nums[fast] == val){// 如果元素值为val，快指针选择下一个++fast;}else{// 如果找到非val元素，将该元素赋值给nums[slow]nums[slow] = nums[fast];++slow;++fast;}}return slow;
   }
   

---

有序数组的平方

1. 循环不变量（循环中的变量的逻辑）
   • 初始化： 迭代前，循环不变量为真
   • 保持： 迭代中，前后状态的转移仍然能保证循环不变量为真
   • 终止： 迭代后，循环不变量可以提供有用结果
2. 逆向思维，充分利用不变的逻辑进行程序的简化。如下题中的从后向前和从两边向中间的遍历方式。
3. leetcode题目：977. 有序数组的平方
   

   vector<int> sortedSquares(vector<int>& nums) {// 用双指针指向两端，从两端向中间进行逼近int left = 0;int right = nums.size()-1;// 从后向前将每次比较较大的填入新的数组中vector<int> res(nums);int index = right;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {res[index--] = nums[left] * nums[left];++left;} else {res[index--] = nums[right] * nums[right];--right;}}return res;
   }

---

滑动窗口

移除元素

1. 滑动窗口：不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果

2. 滑动窗口基本框架

   void slidwindow(vector<int> nums)
   {// 1. 窗口区间为[left, right)int left = 0;int right = 0;// 2. 直到到达窗口右边界while(right < nums.size()){// - 扩大右边界并更新窗口状态...right++;// - 窗口到达什么状态需要收缩while(需要收缩){// - 缩小左边界并更新窗口状态...left++;}}
   }
   

3. leetcode题目：209. 长度最小的子数组
   

   int minSubArrayLen(int target, vector<int>& nums) {int left = 0;int right = 0; int res = INT_MAX;int len = 0;int windows_sum = 0;while(right < nums.size())//窗口区间为[left, right){windows_sum += nums[right];//更新窗口状态right++;while(windows_sum >= target)//收缩窗口{len = right - left;res = min(res, len);windows_sum -= nums[left];//更新窗口状态left++;}}return res == INT_MAX? 0:res;
   }
   

---

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。 不如点赞·收藏·关注一波

---

🚩点此跳转到首行↩︎

参考博客

1. leetcode二分查找
2. 代码随想录
3. 二分查找算法详解
4. 待定引用
5. 待定引用
6. 待定引用
7. 待定引用
8. 待定引用