算法思想

1. 循环不变量原则：[[02.二分查找]]，[[06.螺旋矩阵]]
2. 双指针原则
   • 快慢指针：[[03.移除元素]]
   • 左右指针：[[04.有序数组的平方]]
3. 模拟实现：[[06.螺旋矩阵]]
4. 滑动窗口（个人觉得移动的时候，存在回溯）[[05.长度最小的子数组]]
5. 区间和：[[07.区间和]]，[[08.开发商购买土地]]

数组基础

数组的性质

• 在cpp中是连续分布在内存中的，在Java中则根据虚拟机来具体设置，比如对于 对象数组 可能存在不连续的情况
• 数组删除元素就是覆盖。根据 index 查找元素： O ( 1 ) ， 删除元素

C++中的 vecto r的底层实现是array，实际上是容器。

常用操作

C++

一般C++中就直接用 vector 了：

• 添加元素：
  • push_back(element)：在末尾添加一个元素。
  • emplace_back(args...)：在末尾就地构造一个元素。
• 删除元素：
  • pop_back()：移除末尾的元素。
  • erase(position)：移除指定位置的元素。
  • clear()：移除所有元素。
• 访问元素：
  • v[i] 或 v.at(i)：访问第i个元素。
  • v.front()：访问第一个元素。
  • v.back()：访问最后一个元素。
• 其他操作：
  • size()：返回元素个数。
  • empty()：检查是否为空。
  • resize(new_size)：调整容器大小。

Java

Java中可以直接定义数组，但是我们一般也是使用 List接口，比如 ArrayList， LinkedList 一般都不用；

1. 实现了List接口，顺序的容器；
2. 未实现同步，其余与vector类似的设置；
3. 允许加入 null 元素；
4. ArrayList 扩容规则也是扩容1.5倍，先复制原数组，然后放到新的空间。

ArrayList<Object> 实际上是一个语法糖，所以 ArrayList 可以存放所有的对象，因为运行时的类型实际上是 Object 。

底层的实现

   /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

transient 关键字用于去除自动序列化,因为在传输的过程中只需要传输实际容量的元素，而不用传输整个 capacity 的元素。

扩容实现

删除元素

1. 删除指定位置 ：remove(int index)
2. 删除指定的值的元素：remove(Object o)

最后为了能让被删除的元素被快速GC，将remove指向的元素手动设置为 null

快速失败

为了在并发过程中，防止有多个线程修改了集合中的元素，当发现这个情况时，直接抛出 ConcurrentModificationException 异常

在每个基本操作过程中都设置一个 modCount 的变量，当执行结束之后的 expectCount 不一致时，很容易发现出现了同步的异常。