数组理论基础

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

数组下标都是从0开始的
数组内存空间的地址是连续的（因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址）

二维数组

不同语言内存管理不同，C++中二维数组是连续分布的，Java 不是。

704. 二分查找

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。~~(不是很理解)~~

第一种写法

定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

第二种写法

target 是在一个在左闭右开的区间里，也就是**[left, right)**

// 版本二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

27. 移除元素

暴力解（两层循环）

自己写的错误解
- 第二层循环的遍历范围有误
- 手欠把多打了一个 = ，把赋值写成了判断

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for(int i = 0; i < size; i++) {
            if(nums[i] == val) {
                for(int j = i; j < size; j++) { // 错误1:j只需要遍历到size-1的位置，修改为： j < size-1
                    nums[j] == nums[j+1]; // 错误2:此处应该是=，进行赋值操作
                }
                size--;
                i--;
            }
        }
        return size;

    }
};

正确解

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

双指针法

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

力扣官方题解

由于题目要求删除数组中等于$val$ 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针 $right$ 指向当前将要处理的元素，左指针 $left$ 指向下一个将要赋值的位置。

如果右指针指向的元素不等于 $val$，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；

如果右指针指向的元素等于 $val$，它不能在输出数组里，此时左指针不动，右指针右移一位。

整个过程保持不变的性质是：区间 $[0,left)$ 中的元素都不等于 $val$。当左右指针遍历完输入数组以后，left 的值就是输出数组的长度。

这样的算法在最坏情况下（输入数组中没有元素等于$val$），左右指针各遍历了数组一次。

27.移除元素-双指针法

自己写的错误解
- 按照我的这种写法，慢指针就起不到对数组进行移动的效果，最后只是得到了数组里有几个目标值，得不到删除目标值后的数组
- 正确解更新在下面的代码中

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int slow = 0;
        for (int fast = 0; fast < n; fast++) {
            if(nums[fast] != val) {
              // 添加 nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;

    }
};

数组part01