# 数组与字符串
# 数组
数组是第一个要去认识的数据结构。
作为最简单，最基础的数据结构，大多数的语言都天然地对数组有着原生地表达，JavaScript亦然。这就意味着我们可以对数组做到“开箱即用”。
注意：要对数组格外走点心，毕竟后面需要它帮忙地地方会非常多。
# 数组地创建
大家平时用到最多的方法想必就是直接用 方括号+元素内容这种形式。
const arr = [1, 2, 3, 4]
不过在算法题中，很多时候我们初始化一个数组时，并不知道它内部元素这种情况。这种场景下，要给大家推荐的是构造函数创建数组的方法：
const arr = new Array()
当我们以构造函数的形式创建数组时，若我们像楼上这样，不传任何参数，得到的就会是一个空数组。等价于：
const arr = []
不过咱们使用构造函数，可不是为了创建空数组这么无聊。 我们需要它的时候，往往是因为我们有“创造指定长度的空数组”这样的需求。需要多长的数组，就给它传多大的参数：
const arr = new Array(7)
在一些场景中，这个需求会稍微变得有点复杂—— “创建一个长度确定、同时每一个元素的值也都确定的数组”。这时我们可以调用 fill 方法，假设需求是每个坑里都填上一个1，只需给它 fill 一个1：
const arr = (new Array(7)).fill(1)
// [1, 1, 1, 1, 1, 1, 1]
如此便可以得到一个长度为7，且每个元素都初始化为1的数组
# 数组的访问和遍历
访问数组中的元素，我们直接在中括号中指定其索引即可：
arr[0] // 访问索引下标为0的元素
# 遍历数组
在这里先讲几个常用的
- for 循环
- forEach
- map
for循环
这个是最最基础的操作。我们可以通过循环数组的下标，来依次访问每个值：
const len = arr.length
for (let i=0; i < len; i++) {
// 输出数组的元素值，输出当前索引
console.log(arr[i], i)
}
forEach方法
通过取 forEach 方法中传入函数的第一个入参和第二个入参，我们也可以取到数组每个元素的值及其对应索引：
arr.forEach((item, index)=> {
// 输出数组的元素值，输出当前索引
console.log(item, index)
})
map方法
map 方法在调用形式上与 forEach 无异，区别在于 map 方法会根据你传入的函数逻辑对数组中每个元素进行处理、进而返回一个全新的数组。 所以其实 map 做的事情不仅仅是遍历，而是在遍历的基础上“再加工”。当我们需要对数组内容做批量修改、同时修改的逻辑又高度一致时，就可以调用 map 来达到我们的目的：
const newArr = arr.map((item, index)=> {
// 输出数组的元素值，输出当前索引
console.log(item, index)
// 在当前元素值的基础上加1
return item+1
})
这段代码就通过 map 来返回了一个全新的数组，数组中每个元素的值都是在其现有元素值的基础上+1后的结果。
这里给个小建议：个人推荐如果没有特殊的需要，那么统一使用 for 循环来实现遍历。因为从性能上看，for 循环遍历起来是最快的。
# 二维数组
在数学中，形如这样长方阵列排列的复数或实数集合，被称为“矩阵”。因此二维数组的别名就叫“矩阵”。
在算法题目中，见到“矩阵”时，能够立刻反射出它说的是二维数组。
# 二维数组的初始化
fill的局限性
有同学用 fill 方法用顺了手，就本能地想用 fill 解决所有的问题，比如初始化一个二维数组：
const arr = (new Array(3)).fill([])
console.log(arr)
// [[], [], []]
当你想修改某一个坑里的数组的值的时候：
arr[0][0] = 1
console.log(arr)
// [[1], [1], [1]]
纳尼？
这是为什么呢？
这就要从 fill 的工作机制讲起了。各位要清楚，当你给 fill 传递一个入参时，如果这个入参的类型是引用类型，那么 fill 在填充坑位时填充的其实就是入参的引用。
其实这3个数组对应了同一个引用、指向的是同一块内存空间，它们本质上是同一个数组。因此当你修改第0行第0个元素的值时，第1-3行的第0个元素的值也都会跟着发生改变。
# 初始化一个二维数组
本着安全的原则，这里我推荐大家采纳的二维数组初始化方法非常简单（而且性能也不错）。直接用一个 for 循环来解决：
const arr = arr.lemgth
for(let i = 0; i < len; i++) {
arr[i] = []
}
for 循环中，每一次迭代我们都通过“[]”来创建一个新的数组，这样便不会有引用指向问题带来的尴尬。
# 二维数组的访问
访问二维数组和访问一维数组差别不大，区别在于我们现在需要的是两层循环：
// 缓存外部数组的长度
const outerLen = arr.length
for(let i=0;i<outerLen;i++) {
// 缓存内部数组的长度
const innerLen = arr[i].length
for(let j=0;j<innerLen;j++) {
// 输出数组的值，输出数组的索引
console.log(arr[i][j],i,j)
}
}
一维数组用 for 循环遍历只需一层循环，二维数组是两层，三维数组就是三层。依次类推，N 维数组需要 N 层循环来完成遍历。
# 数组与字符串转化
数组和字符串是最基本的数据结构，在很多编程语言中都有着十分相似的性质，而围绕着它们的算法面试题也是最多的。
很多时候，在分析字符串相关面试题的过程中，我们往往要针对字符串当中的每一个字符进行分析和处理，甚至有时候我们得先把给定的字符串转换成字符数组之后再进行分析和处理。
举例：翻转字符串“algorithm”。
解法：用两个指针，一个指向字符串的第一个字符 a，一个指向它的最后一个字符 m，然后互相交换。交换之后，两个指针向中央一步步地靠拢并相互交换字符，直到两个指针相遇。这是一种比较快速和直观的方法。
注意：由于无法直接修改字符串里的字符，所以必须先把字符串变换为数组，然后再运用这个算法。
# 数组的优缺点
要掌握一种数据结构，就必须要懂得分析它的优点和缺点。数组的优点在于：
构建非常简单
能在 O(1) 的时间里根据数组的下标（index）查询某个元素
而数组的缺点在于：
构建时必须分配一段连续的空间
查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数）
删除和添加某个元素时，同样需要耗费 O(n) 的时间
所以，当你在考虑是否应当采用数组去辅助你的算法时，请务必考虑它的优缺点，看看它的缺点是否会阻碍你的算法复杂度以及空间复杂度。
# 例题分析
LeetCode 第 242 题：给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。
说明：你可以假设字符串只包含小写字母。
示例 1
输入: s = "anagram", t = "nagaram"
输出: true
示例 2
输入: s = "rat", t = "car"
输出: false
字母异位词，也就是两个字符串中的相同字符的数量要对应相等。例如，s 等于 “anagram”，t 等于 “nagaram”，s 和 t 就互为字母异位词。因为它们都包含有三个字符 a，一个字符 g，一个字符 m，一个字符 n，以及一个字符 r。而当 s 为 “rat”，t 为 “car”的时候，s 和 t 不互为字母异位词。
解题思路
一个重要的前提“假设两个字符串只包含小写字母”，小写字母一共也就 26 个，因此：
可以利用两个长度都为 26 的字符数组来统计每个字符串中小写字母出现的次数，然后再对比是否相等；
可以只利用一个长度为 26 的字符数组，将出现在字符串 s 里的字符个数加 1，而出现在字符串 t 里的字符个数减 1，最后判断每个小写字母的个数是否都为 0。
按上述操作，可得出结论：s 和 t 互为字母异位词。
# 剑指offer关于数组 & 字符串 的题目
# 数组
- 数组中重复的数字**（P39）
在一个长度为n的数组里，所有的数字都在0~n-1范围内，数组中某些数字是重复出现的，但不知道有几个数字重复出现了，也不知道每个数字重复出现了几次，请找出这个重复的数字。
例如，如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出的重复数字是2或者3；
- 不修改数组找出重复的数字（P41）
在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。 请找出数组中任意一个重复的数字，但不能修改输入的数组。 例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
- 二维数组中的查找（P44）
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
# 字符串
- 替换空格（P51）
请实现一个函数，把字符串中的每个空格图换成“%20”
例如：输入“We are happy"，则输出“We%20are%20happy"