一、概念：
数组是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据。
1、了解线性表（每个数据最多只有一个前驱和后继节点，eg 数组、链表、队列、栈等）和非线性表（eg 树、堆、图）
2、连续的内存空间和相同数据类型的数据，这两点使得数组可以实现随机访问。
二、操作：
随机访问：
根据下标随机访问的时间复杂度为O（1）。
根据数组的示意图，可知根据下标即可知道该元素的地址，具体计算公式为 num[index]_addr = base_addr + data_type_size * index 。
插入：
在确保数组有空间的情况下进行插入：
1、如果确保数组数据的顺序，在某个位置K插入某个数，需要把插入位置K以及以后的数据移动，平均复杂度为O（n）。
2、如果对原数组数据顺序没有要求，直接在最后位置插入一个数，然后和第K个数进行调换即可，时间复杂度为O（1）。
删除：
删除数据，数据需要向前运动，平均时间复杂度为O（n）
1、删除最后一个元素，时间复杂度为O（1）
2、删除第一个元素，时间复杂度为O（n）
3、如果有多次删除操作，可以考虑合并提高效率
三、注意点：
1、数据的越界问题，数组下标从0开始，下标取值范围[0,1,2,...len-1]
2、多维数组
3、学习高级语言的容器，对数组的封装以及动态的扩容，java的arraylist、C++的vector
四、常见面试题：
例题1： 1207. 独一无二的出现次数https://leetcode-cn.com/problems/unique-number-of-occurrences/
给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
示例 1：
输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
示例 2：
输入：arr = [1,2]
输出：false
示例 3：
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true
思路1：判断哈希的长度和set的长度
思路2：哈希计数 + 数组排序
思路3：哈希计数 + set 重复判断
时间复杂度：O（n）
空间复杂度：O（n）
代码实现：
# 思路1：判断哈希的长度和set中的长度
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
dic = Counter(arr)
return len(dic) == len(set(dic.values()))
# 思路2：哈希计数+数组排序
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
dic = Counter(arr)
nums = list(dic.values())
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return False
return True
# 思路3：哈希计数+ set重复判断
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
dic = Counter(arr)
arr = list(dic.values())
visited = set()
for i in range(len(arr)):
if arr[i] not in visited:
visited.add(arr[i])
else:
return False
return True
例题2： 349. 两个数组的交集 https://leetcode-cn.com/problems/intersection-of-two-arrays/
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
思路一： 哈希计数+set去重
思路二： 两个set去重
思路三： 逻辑判断
思路四： 哈希计数 用map[j] = 0 保证去重
代码实现：
方法一：哈希计数+set去重
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
dic = Counter(nums1)
nums2 = list(set(nums2))
res = []
for i in range(len(nums2)):
if nums2[i] in dic.keys():
res.append(nums2[i])
return res
方法二：两个set去重
写法1：
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
写法2：
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1 = list(set(nums1))
nums2 = list(set(nums2))
return [i for i in nums1 if i in nums2]
方法三：逻辑判断
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = []
for i in nums1:
if i not in res and i in nums2:
res.append(i)
return res
方法四：哈希计数 用map[j] = 0 保证去重
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = []
map = {}
for i in nums1:
map[i] = map[i]+1 if i in map else 1
for j in nums2:
if j in map and map[j] > 0:
res.append(j)
map[j] = 0
return res
例题3：1122. 数组的相对排序https://leetcode-cn.com/problems/relative-sort-array/
给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
思路1：新建数组计数排序， T：O（m+n）, S：O（1）
思路2：用map计数排序， T：O（logm + n）， S：O（max(m,n)）
代码实现：
# 思路一
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
arr = [0] * 1001
res = []
for i in range(len(arr1)):
arr[arr1[i]] += 1
for i in range(len(arr2)):
while arr[arr2[i]] > 0:
arr[arr2[i]] -= 1
res.append(arr2[i])
for i in range(len(arr)):
while arr[i] > 0:
res.append(i)
arr[i] -= 1
return res
# 思路二
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
dif= [i for i in arr1 if i not in arr2]
dif.sort()
res = []
arr1_cnt = collections.Counter(arr1)
for i in arr2:
res += [i] * arr1_cnt[i]
res += dif
return res
例题4：1. 两数之和：https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路1：暴力求解法，两层遍历，循环，如果nums[i] + nums[j] == target, return [i, j]， T：O（n^2）, S：O（1）
思路2：哈希表查询，T：O（n）， S：O（n）
代码实现：
# 思路一：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
# 思路二：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(nums)):
if target - nums[i] in dic.keys():
return [dic[target - nums[i]], i]
else:
dic[nums[i]] = i
例题5：922. 按奇偶排序数组 II https://leetcode-cn.com/problems/sort-array-by-parity-ii/
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
思路：
双指针法，even记录偶数的下标， odd记录奇数的下标；遍历数组，位运算 & 1 == 1为奇数， & 1 == 0 为偶数；放入到结果数据集中。
T：O（n）， S：O（n）额外开辟一个长度为n的数组记录返回集。
代码实现：
class Solution:
def sortArrayByParityII(self, A: List[int]) -> List[int]:
res = [0] * len(A)
even, odd= 0, 1
for i in range(len(A)):
if A[i] & 1 == 1:
res[odd] = A[i]
odd += 2
else:
res[even] = A[i]
even += 2
return res
例题6：15. 三数之和 https://leetcode-cn.com/problems/3sum/
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路：
思路：排序 + 双指针，+ 去重； 先对数组进行排序，排序后用双指针左右夹逼的方法进行遍历。遍历时注意两次判重，第一次判重是判断第一个元素，重复时continue跳过。第二次判重是在左指针和右指针，重复时左右指针分布+1，和-1跳过。
T：O（nlogn）， S：O（1）
代码实现：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
nums.sort()
if nums[0] > 0:
return []
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i+1, len(nums) - 1
while left < right:
count = nums[i] + nums[left] + nums[right]
if count < 0:
left += 1
elif count > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
return res
例题7：66. 加一 https://leetcode-cn.com/problems/plus-one/
思路：
判断各位是否为9，如果不为9的话，+1 返回结果；如果不为9的话，变成0. 如果循环结束仍未返回的话，则新建一个数组，长度+1， 首位为1，其余为0，返回。
T：O（n）， S：O（n）
代码实现：
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits) - 1, -1, -1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
digits = [0] * (len(digits) + 1)
digits[0] = 1
return digits
例题8： 283. 移动零 https://leetcode-cn.com/problems/move-zeroes/
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
思路：
单指针，标记非零元素的下标， [0,1,0,3,12] 非零元素1， 3， 12的下标依次就是 0， 1， 2。
T：O（n）
S：O（1）
代码实现：
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
j = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[i], nums[j] = nums[j], nums[i]
j += 1
例题9： 349. 两个数组的交集 https://leetcode-cn.com/problems/intersection-of-two-arrays/
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
思路：
思路：用set分别对nums1和nums2去重，然后nums1转成list，并遍历，如果遍历的元素在nums2的set中，则加入返回的结果集中。
T：O（n） ， S：O（n）
代码实现：
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = []
nums1 = list(set(nums1))
nums2 = set(nums2)
for num in nums1:
if num in nums2:
res.append(num)
return res
例题10： 127. 单词接龙 https://leetcode-cn.com/problems/word-ladder/
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。
思路：
思路：双端队列，初始装入开始遍历的单词，和长度1。 循环时，从双端队列的左端弹出元素，如果弹出的单词和目标单词相同则，返回当前的长度。如果不同，则遍历当前单词，对每个字符一次进行变换，每变换一次验证一下是否在字典集中，是否访问过。如果之前未访问过，又在字典集中，则装入双端队列中，长度+1.
如果为未找到，则返回0.
T：O（n*c^2），n为单词的个数，c为单词的平均长度
S：O（n），n为单词的个数
代码实现：
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
visited = set()
deque = collections.deque([(beginWord, 1)])
alpha = string.ascii_lowercase
while deque:
word, length = deque.popleft()
if word == endWord:
return length
for i in range(len(word)):
for ch in alpha:
new_word = word[:i] + ch + word[i+1:]
if new_word not in visited and new_word in words:
visited.add(new_word)
deque.append((new_word, length + 1))
return 0
例题11： 347. 前 K 个高频元素 https://leetcode-cn.com/problems/top-k-frequent-elements/
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
思路：
思路：哈希计数， 计数结果按values的大小进行反向排序，取出前k个高频的keys值
T：O（k）， S：O（n），n为不同元素的个数
代码实现：
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dic = Counter(nums)
li = sorted(dic.items(), key = lambda kv : kv[1], reverse = True)
re = []
for i in range(k):
re.append(li.pop(0)[0])
return re
例题12： 剑指 Offer 59 - I. 滑动窗口的最大值 https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
思路：
思路：用双端队列，队列里存的是数组元素的下标，永远保持队列里的最左端是最大的元素
T：O（n） ， S：O（k）
代码实现：
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res, deque = [], []
for i in range(len(nums)):
while deque and nums[i] > nums[deque[-1]]:
deque.pop()
deque.append(i)
while i - deque[0] > k - 1:
deque.pop(0)
if i >= k - 1:
res.append(nums[deque[0]])
return res
例题13： 455. 分发饼干 https://leetcode-cn.com/problems/assign-cookies/
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
思路：
思路：贪心算法，最大的饼干，优先满足胃口最大的小孩子，对两个数组同时进行倒序遍历
T：O（n）， S：O（1）
代码实现：
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
j = len(s) - 1
count = 0
for i in range(len(g) -1, -1, -1):
if j >=0 and s[j] >= g[i]:
j -= 1
count += 1
return count
撰写记录
2020.12.05-08:00:01-第一次撰写
2020.12.14-07:28:10-第二次撰写
2020.12.15-07:27:15-第三次撰写
2020.12.23-06:02:08-第四次撰写
2020.12.24-07:28:09-第五次撰写
2020.12.26-10:35:10-第六次撰写
2021.01.03-08:03:00-第七次撰写
2021.01.06-07:05:00-第八次撰写
2021.02.01-19:40:00-第九次撰写
