# 数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合，下标从 0 开始。

增添或者删除数组元素时不可避免的要移动其他元素的地址，因此数组的元素实际上不是删除，而是覆盖。

二维数组的内存空间地址在 C++ 中也是连续的。

# 二分查找

题目链接

难点：根据区间定义做边间处理

两种区间：左闭右闭 [left, right]，左闭右开 [left, right)。两种区间内的元素都是相同的，只是表达方式不同。

	class Solution {
	public:
	int search(vector<int>& nums, int target) {
	int mid = 0;
	int left = 0, right = nums.size() - 1; // [left, right]
	while(left <= right) { //left == right 时，区间 [left, right] 依然有效
	mid = (left + right) / 2;
	if(target == nums[mid]) return mid; // 找到 target，返回下标
	else if(target > nums[mid]) left = mid + 1; //target 比中值大，找右半区间
	else right = mid - 1; //target 比中值小，找左半区间
	}
	return -1;
	}
	};

	class Solution {
	public:
	int search(vector<int>& nums, int target) {
	int mid = 0;
	int left = 0, right = nums.size(); // [left, right)
	while(left < right) { //left == right 时，区间 [left, right) 无效
	mid = (left + right) / 2;
	if(target == nums[mid]) return mid; // 找到 target，返回下标
	else if(target > nums[mid]) left = mid + 1; //target 比中值大，找右半区间
	else right = mid; //target 比中值小，找左半区间
	}
	return -1;
	}
	};

题目链接

时间复杂度 $O(n^2)$ 。

	class Solution {
	public:
	int removeElement(vector<int>& nums, int val) {
	int len = nums.size();
	for(int i = 0; i < len; i++) {
	if(nums[i] == val){ // 发现要移除的元素，整体向前移一位
	for(int j = i + 1; j < len; j++){
	nums[j - 1] = nums[j];
	}
	len--;
	i--;
	}
	}
	return len;
	}
	};

	class Solution {
	public:
	int removeElement(vector<int>& nums, int val) {
	int slowIndex = 0, fastIndex = 0;
	while(fastIndex < nums.size()) {
	// 当碰到要移除的元素时，快指针走，慢指针不动
	// 否则两指针一起移动
	if(nums[fastIndex] != val) {
	nums[slowIndex++] = nums[fastIndex];
	}
	fastIndex++;
	}
	return slowIndex;
	}
	};

题目链接

数组有序，但包含负数。左端值平方后可能会成为最大值。

不能原地更新：原地更新的实质是暴力。以空间换时间，增添一个新数组来保存平方后的值。

	class Solution {
	public:
	vector<int> sortedSquares(vector<int>& nums) {
	vector<int> result(nums.size(), 0);
	int n = nums.size() - 1;
	int left = 0, right = nums.size() - 1;
	while(left <= right) { // 最后还有两个元素要比较
	// 数组从右往左开始放值
	// 左右两值比较，最大的放入数组
	if(nums[left] * nums[left] < nums[right] * nums[right]) {
	result[n--] = nums[right] * nums[right];
	right--;
	}
	else {
	result[n--] = nums[left] * nums[left];
	left++;
	}
	}
	return result;
	}
	};