数组总结篇

Doublew2w大约 5 分钟

什么是数组？

数组是存放在「连续内存空间」上的「相同类型数据」的集合。

数组的特点

索引从 0 开始

内存地址是连续

访问元素： $O(1)$

插入和删除元素: $O(n)$

二分法

二分查找模板 1

public int binarySearch(int[] nums, int target){
  int left = 0;
  int right = nums.length - 1; // 注意 1
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){
        return mid;
    }
    else if(nums[mid] < target) {
        left = mid + 1; // 注意
    }else if(nums[mid] > target){
        right = mid - 1;  // 注意
    }
  }
  // End Condition: left > right
  return -1;
}

初始化条件：left = 0, right = nums.length - 1 ，相当于闭区间 $[left,right]$ ，而这个区间就是我们的「搜索区间」
循环停止条件：
nums[mid] == target
如果没有找到的情况下，「搜索区间」不存在。即 left > right => $[right+1,right]$ ，区间不存在

如果非要用 while(left < right)，我该怎么办？

 //...
while(left < right) {
    // ...
}
return nums [left] == target ? left : -1;

分析如下：

当退出循环时，存在 left == right ，不管是因为什么原因导致的， 左元素还是右元素最终有一个没做判断

left = mid + 1 ，所以才有 left == right 退出循环
right = mid - 1 ，所以才有 left == right 退出循环

向左查找，向右查找：在上面的「搜索区间」情况下，当 nums[mid] 查找不到时，此时 mid 已经被判断了。因此下次「搜索区间」应该是 $[left,mid-1]$ 或者 $[mid+1,right]$

二分查找模版 2：找满足条件的最左侧的值

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

初始化条件：left = 0, right = nums.length ，每次循环的「搜索区间」是 [left, right) 左闭右开
循环停止条件：left == right， $[left,left)$ 区间为空，搜索停止。
向左查找：nums[mid] > target，nums[mid] == target 都会改变 right 的值。其实相当于告诉我们 nums[mid] 的值都在 target 的右侧。只有这样做，我们才能不断地 缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

如果 target 在数组中，最后返回的结果 left 表示，数组中小于 target 的元素有 left 个，也可以表示 target 最左的下标为 left

如果 target 不在数组中，假设一种极端情况

[2,5,7,8]
target = 1

在循环过程中，left 一直保持不变，而 right 一直向左边靠近，最终 left == right 最后循环，最后返回 left = 0。

含义是：数组中小于 1 的元素有 0 个。

综上可以看出，函数的返回值（即 left 变量的值）取值区间是闭区间 $[0,nums.length]$

while (left < right) {
    //...
}
// target 比所有数都大
if (left == nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] == target ? left : -1;

//if(left != nums.length && nums [left] == target){
    //return left;
  //}
  //return -1;

二分查找模版 3：找满足条件的最右侧的值

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

当 nums[mid] == target 时，不要立即返回，而是 增大「搜索区间」的下界 **left**，使得区间不断向右收缩，达到锁定右侧边界的目的。

由于我们更新 left 是 left = mid + 1，那就出现一种情况，left = mid + 1 = right 越界退出循环。

nums[left] 一定不等于 target，否则也不会导致 left = mid+ 1 的操作发生
nums[left-1] 有可能是 target，所以要进行 后处理检查

双指针法

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

滑动窗口

根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将 $O(n^2)$ 的暴力解法降为 $O(n)$ 。

最小/最大子数组问题
字符串模式匹配问题
固定长度的子数组/子字符串问题
固定长度的子数组/子字符串问题

模拟行为

模拟类的题目在数组中很常见，不涉及到什么算法，就是单纯的模拟。

循环不变量原则，其实这也是写程序中的重要原则。