实现动态数组：

需要实现的功能：push, pop, size, index。

因为是动态的，意味在数组大小是无限的，难点在于不可能无限申请内存。

解决方案：先初始化一个长度为n的数组，当数组满了时，建立一个长度为2n的数组，并将原来的数据复制到这个2n数组内。

建立一个名为dymanic_array的类，具体类里面的method有：

我们来看具体的题目

第三个数‘１’在数组中是第二次出现，而第一次出现１的下标是０．因此输出第三位为０．

naive解法:

拿到题目一般思考方法：想一个边界情况有助于打开思路。这里的边界情况是输入为空数组。

O(n)解法

第二次遍历在过程可以改为记录每个数的位置，然后直接比较。

具体的代码为：enumerate()函数每次loop返回一个tuple, (i, num)，i为counter, num遍历数组里的元素。

类型题：

1. dict里面储存出现次数而不是下标。2. 不断更新dict里的下标就行了。3.sum[i]表示前i个数字的合，结果为sum[place i] - sum[place j]-1

类型1, 将dict储存为次数 每出现一次加一

Leetcode 实战

解题的通用思考过程：

1. 考虑边界情况。这里n>1, 无边际情况。

2. 题目有限制条件的话，可以先思考没有限制的解法。这里用除法的话是这样的：

没有限制的解法

3. 考虑暴力解法(naive approach)

4.你的暴力解法里面有什么冗余的，重复计算的部分，找到它，想一个更优的解法。

算法与代码：

4. 利用前i+1的乘积等于前i的乘积乘与i+1. 但是目前这个算法有左积，右积和返回的数组

空间优化版：