数据结构与算法 - 数组与二分查找 + Leetcode典型题

1. 什么是数组

数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
C++中二维数组在地址空间上也是连续的。

需注意：

• 数组的下标从0开始。
• 数组内存空间的地址是连续的。
• 数组的元素是不能删的，只能覆盖。

2. 二分查找

力扣题目链接
之前的题解704. 二分查找中有一些地方不够清晰，此处补充说明。
数组为有序数组+数组中无重复元素 -> 考虑二分法

1. 在计算mid时，考虑数据溢出的可能，应将mid = (low + high) / 2;写为

	int mid = left + ((right - left) / 2); //防止溢出

2. 二分法根据选择的区间不同，有两种解决方式，分别为：左闭右闭 [left, right] 和左闭右开 [left, right)

• 在左闭右闭 [left, right] 的情况下，nums [right] 表示数组中最后一个元素，while (left <= right) 要使用 <= ，因为 left == right 是有意义的。且每次判断if (nums[mid] > target) 后，由于nums[mid] 一定不是target ，right 要赋值为 middle - 1，right = mid - 1;，这表示下一次要查找的左区间结束下标位置为 middle - 1，即区间为 [left, middle - 1]。
  同理，if (nums[mid] < target)时， left 要赋值为 middle + 1。

• 在左闭右开 [left, right) 的情况下，nums [right] 无意义，while (left < right)中使用**<**，因为 left == right 在区间 [left, right) 是没有意义的。每次判断if (nums[mid] > target) 后，nums[mid] 不等于target ，在左区间 [left, mid) 中继续寻找.
  区间右开：right更新为mid。
  区间左闭：if (nums[mid] < target)时，left 要更新为 mid + 1

3. 二分查找时间复杂度为 O(log n)

相关题目1：35. 搜索插入位置
补充之前题解35. 搜索插入位置-二分查找中表达不清晰的地方。
这道题存在四种情况：

1. 目标值在数组所有元素之前
2. 目标值等于数组中某一个元素
3. 目标值插入数组中的某一位置
4. 目标值在数组所有元素之后

与上一道题的差别在于1，3，4情况下的返回值。在左闭右闭 [left, right] 的情况下，right = mid - 1;，（1情况下此时 right = -1；3情况下 right 指向应插入的前一个位置；4情况下 right 指向最后一个元素的位置）所以应返回 right + 1 ，即return right + 1;；在左闭右开 [left, right) 的情况下，right = mid;，所以应返回 right ，即return right;。

相关题目2：69.x的平方根 367.有效的完全平方数
题解：【LeetCode-简单】69.x的平方根 + 367.有效的完全平方数 - 二分法

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

3. 移除元素 - 双指针

力扣题目链接
题解：【LeetCode-简单】27.移除元素 - 数组与双指针法

由于Leetcode中数组是用的vector，这道题可以用nums.erase(it);函数暴力破解，但要注意erase()函数在删除元素后会将位于该元素后方的剩余元素前移，这将导致数组长度的改变以及后续元素下标的变化，删除元素后迭代器 it 不需要 it++便已经指向了下一个元素。

不考虑vector的因素，由于数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。本题可采用双指针的方法。

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

下面定义本题中的快慢指针：

• 快指针：寻找新数组（不含有目标元素的数组）的元素 ，即用于寻找不等于val的元素
• 慢指针：指向更新新数组下标的位置，即指向需要被覆盖的等于val的元素

最终慢指针一定指向了最终数组末尾的下一个元素，只要返回慢指针即可。
题目中提及元素的顺序可以改变，同向双指针和相向双指针都可以使用，如果要求不能改变元素顺序，则应该使用同向双指针。

4. 有序数组的平方 - 双指针

力扣题目链接
典型的双指针问题，暴力解法的时间复杂度是O(nlogn)，而采用双指针的时间复杂度是O(n)。
题解：【LeetCode-简单】977. 有序数组的平方-双指针

5. 长度最小的子数组 - 滑动窗口

力扣题目链接

题解：【LeetCode-中等】209.长度最小的子数组-双指针/滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成了一个不断搜索区间的过程。滑动窗口只用一个for循环来完成这个操作。

而这个循环的索引，一定是表示 滑动窗口的终止位置。

直观的动画演示：

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

	while (sum >= s) {
		subLength = (j - i + 1); //取子序列的长度
		result = result < subLength ? result : subLength;
        这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
        sum -= nums[i++]; 
	}

6. 螺旋矩阵II - 模拟

力扣题目链接
题解：【LeetCode-中等】59.螺旋矩阵II - 二维数组

本题并不涉及到什么算法，就是模拟过程，还要注意边界情况。