数组

本篇博客只记录刷题思路不记录具体代码
题目来源代码随想录
刷完感想：今天去吃烤肉拌饭🤤

:::tip 和数组题相关的提示

  1. 数组是存放在连续内存空间上的相同类型数据的集合。
  2. 可以靠索引快速定位
  3. 双指针
    :::

二分查找

典型，但是思路好像还是没跟上

注意区间的左闭右开会影响很多东西

没事之前已经把能踩的坑都踩过一遍了（https://www.yuque.com/kixuan/yy8qei/lpansi5g3iogf6tr

这里重新贴一下用于警醒自己😰

哈哈服了写个二分查找写出了一堆问题，来看你写的破代码！🥰🥰
原代码

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

‼️问题分析‼️
最重要的确定你的区间是 [ , ] 还是 [ , )，这会影响 mid、left、right 的更改

  1. 初始 mid 计算错误： mid 不正确，应在每次循环内计算 mid。
    int mid = left + (right - left) / 2;
  2. 循环条件错误：在进行二分查找时，应该使用 <=
    这里是因为你设置的区间是 [left,right]，=的时候有意义，所以是<=
    while (left <= right) {
  3. mid 更新逻辑错误： 更新 left 和 right 时，不应将 mid 直接赋值给 left 或 right，应调整为 mid + 1 或 mid - 1，否则可能会导致死循环
    if (nums[mid] < target) left = mid + 1;
    if (nums[mid] > target) right = mid - 1;
  4. 返回值错误： 在循环结束后，mid 可能不代表目标插入位置，应返回 left，因为 left 是当前查找区间的起始位置。

修正代码

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

发表重大感想：
把能踩的坑全踩了一遍！！牛！！！🥳🥳🥳🥳

移除元素

经典同向双指针，直接在原数组上更新就行

有序数组的平方

还是双指针，但是注意这次得新开一个数组

还得根据给出数组的特征改成异向双指针

螺旋矩阵

模拟，思路不难但是也要注意左闭右开，看你自己最近一次提交更容易理解

区间和

前缀和思路没想到，用的确实不多