「面试指南」JS数组Array常用算法,Array算法的一般解答思路
小小👨💻 人气:0
#### 先看一道面试题
在 LeetCode 中有这么一道简单的数组算法题：
```javascript
// 给定一个整数数组 nums 和一个目标值 target，
// 请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
// 你可以假设每种输入只会对应一个答案。
// 但是，你不能重复利用这个数组中同样的元素。
// 示例:
// 给定 nums = [2, 7, 11, 15], target = 9;
// 因为 nums[0] + nums[1] = 2 + 7 = 9,
// 所以返回 [0, 1]。
```
对于上述的面试题，对于我们前端开发，不同的解法，有着不同的技术水准。
那么到底有几种常用解法？实践并汇总了以下几种方法：
- 暴力双 for 循环解法；
- 单循环 indexOf 优化；
- 单循环 obj 优化；
- 单循环 map 优化；
- 单循环尾递归优化；
#### 暴力双 for 循环破解
```javascript
// 两层循环判断，找出当前元素cur与target-cur的，满足放入result结果中
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
const cur = nums[i];
for (let j = 0; j < nums.length; j++) {
const others = nums[j];
// 因为是不可以重复利用同样的元素，所以i!==j;
if (others == target - cur && i !== j) {
// 因为是我们只找出一个结果，所以我们找到后，直接返回结果
return [i, j];
}
}
}
// 如果未找到，返回[]
return [];
}
// 测试结果
let result = twoSum([2, 7, 11, 15], 9);
console.log(result); // [0,1] 2,7 满足结果，所以返回其下标[0,1]
```
时间复杂度：O(n^2),可能看似感觉还不错，但是执行时间长，内存占用也不小，当 nums 数组足够大时，它的性能瓶颈就会体现出来。
leetCood 测试结果：
#### 单循环 indexOf 优化；
```javascript
// 单循环判断，找出当前元素cur，与target-cur是否相等，满足放入result结果中
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
let cur = nums[i],
others = target - cur, // 期望目标值
others_index = nums.indexOf(others);
// 判断期望目标值是否在nums中，因为不能是它本身，要校验两个下标不能相等
if (others_index > -1 && i !== others_index) {
// 因为是我们只找出一个结果，所以我们找到后，直接返回结果
return [i, others_index];
}
}
// 如果未找到，返回[]
return [];
}
// 测试结果
let result = twoSum([2, 7, 11, 15], 9);
console.log(result); // [0,1] 2,7 满足结果，所以返回其下标[0,1]
```
时间复杂度：O(n^2),因为 indexOf()方法的时间复杂度为 O(n),所以和上述暴力破解只是写法上区别了。执行时间，内存占用依然存在可优化的空间。
leetCood 测试结果：
#### 单循环 obj 优化：
使用 obj，边存边比较目标差值是否在 obj 中。如果存在，直接返回下标，不存在继续边存边比，直到结束循环；
```javascript
function twoSum(nums, target) {
let obj = {};
for (let i = 0; i < nums.length; i++) {
if (obj[target - nums[i]] >= 0) {
return [obj[target - nums[i]], i];
}
obj[nums[i]] = i;
}
return [];
}
// 测试结果
let result = twoSum([2, 7, 11, 15], 9);
console.log(result); // [0,1] 2,7 满足结果，所以返回其下标[0,1]
```
时间复杂度：O(n),由于对象键值对 key-value 的优越性，对于作为查找类的算法很有优势。时间复杂度降为原有的一倍，性能会好一些。
leetCood 测试结果(较上优化了 90ms 左右)：
#### 单循环 map 优化：
上述我们使用了一个对象作为查找的依据，同样的我们可以根据 map 替换，来破解。
```javascript
function twoSum(nums, target) {
let map = new Map();
// 遍历nums 放入 map中
for (let i = 0; i < nums.length; i++) {
let value = nums[i];
map.set(value, i);
}
for (let j = 0; j < nums.length - 1; j++) {
if (map.has(target - nums[j]) && map.get(target - nums[j]) != j) {
return [j, map.get(target - nums[j])];
}
}
// 不符合，返回空数组
return [];
}
// 测试结果
let result = twoSum([2, 7, 11, 15], 9);
console.log(result); // [0,1] 2,7 满足结果，所以返回其下标[0,1]
```
时间复杂度：O(2n),第一次循环时间度 n,第二次为 n\*1，故为 O(2n), 由于 map 的特殊数据结构，故作为查找类的算法，相比 obj 具有绝对优势。
leetCood 测试结果(较上再次优化了 近 30ms)：
#### obj 尾递归优化；
我们对于上面单循环 obj 做下改造，利用尾递归的方式破解：
```javascript
var twoSum = function(nums, target, i = 0, objs = {}) {
const obj = objs; //存在期望数字;
// 判断obj中是否
if (obj[target - nums[i]] >= 0) {
// 存在直接返回两值的下标;
return [obj[target - nums[i]], i];
} else {
// 不存在，存入obj
obj[nums[i]] = i;
// 递归继续查找
if (i < nums.length - 1) {
// i 自增
i++;
return twoSum(nums, target, i, obj);
} else {
// 递归结束，未查询到结果
return [];
}
}
};
```
时间复杂度：O(n),假设我们查找到,则递归的次数应该是最多的为 n，所以时间复杂度 O(n);
递归相比于 for 循环是一种更近层次的查找，在树结构数据、多维数组中我们常用递归思想来处理数据。
leetCood 测试结果(结果为 52ms)，多次执行测试大都在 60ms 上下，说明了递归思想的优势：
#### map 尾递归优化破解；
我们同时对单循环 map 的也是用递归，看看会发生什么结果？
```javascript
var twoSum = function(nums, target, i = 0, maps = new Map()) {
const map = maps;
// 判断obj中是否
if (map.has(target - nums[i])) {
// 存在直接返回两值的下标;
return [map.has(target - nums[i]), i];
} else {
// 不存在，存入obj
map.set([nums[i]], i);
// 递归继续查找
if (i < nums.length - 1) {
// i 自增
i++;
return twoSum(nums, target, i, map);
} else {
// 递归结束，未查询到结果
return [];
}
}
};
```
时间复杂度：O(n),假设我们查找到,则递归的次数为 n，所以时间复杂度也为 O(n);
leetCood 测试结果(最快结果为 44ms)，多次执行测试大都在 60ms 上下，与上一个性能相似：
当然，测试结果只是一个参考可能不太准确，不过通过多次测试也是可以看出他们之间的差距的。
#### 总结：
以上我们使用了暴力破解、单循环 obj、单循环 map、obj 尾递归、map 尾递归做了对比。
一般对于数组的算法，几乎都可以使用上次思路来解决，当然我们要知道衡量算法指标时间复杂度 O()、空间复杂度 S()。
> 空间复杂度：算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n 为问题的规模，f(n)为语句关于 n 所占存储空间的函数。
>
> 通常，我们都是用“时间复杂度”来指运行时间的需求，是用“空间复杂度”指空间需求。
>
> 当直接要让我们求“复杂度”时，通常指的是时间复杂度。不过，在一定程度上我们也要考虑算法所需存储空间。
在面试中与实际工作中，简单数组算法的几点经验之谈：
数组去重：使用单循环，结合 obj 或 map 做中间辅助判断；
数组扁平化：使用递归；
树结构的查找与处理：单循环使用 obj/map 做中间辅助判断，同时结合递归思想；
数组的特定重组：除了上述思想外，可能要结合数组常用方法：indexOf(),map(),forEach()或数组高阶函数 filter(),reduce(),sort(),every(),some()等。本文只是抛出一个算法的思路，不再做长篇大论的演示。
```javascript
// 递归思路
// 最简递归:for循环形式
function recursive_simple(array) {
for (let i = 0; i < array.length; i++) {
const item = array[i];
// 进入递归ifEntry:递归条件,subArray:递归参数
if (ifEntry) {
// do something
recursive_simple(subArray);
} else {
// 跳出递归
// do something
}
}
}
// 尾递归
function recursive_tail(array, i = array.length - 1, others) {
const other = others;
/https://img.qb5200.com/download-x/do something
// 进入递归，others:其他参数,可以obj、map等一些中间临时变量
if (i > 0) {
// do something
console.log(i, array[i]);
i--;
// 递归调用
return recursive_tail(array, i, others);
}
}
```
#### 涉及方法：
indexOf():检测 searchString 在 string、array 是否存在，不过时间复杂度 O(n);
map:数组的遍历，返回新的数组，需要手动 return 当前 item;对于数组中对象的 key-value 改写比较适合，时间复杂度 O(n);
forEach:改写当前数组，不需要 return，对于直接改写某个数组比较合适；
filter：过滤函数，对于过滤数组中符合某个条件的子项比较合适；
reduce:接收一个函数作为累加器(accumulator)，返回具体数值，对于需要对数组某些子项操作的比较合适，比如求和，斐波那契数列等的处理,
reduce(function(total, currentValue, currentIndex, arr), initialValue);
sort:适合数组中，复杂比较关系的，一般用于排序用途；
every：数组迭代方法，对数组中每一项运行给定函数，如果该函数对每一项返回 true,则返回 true;
some:数组迭代方法，对数组中每一项运行给定函数，如果该函数对任一项返回 true,则返回 true，与 every 有区别，如其名：every:每一项，some:任一项;
微信公众号：前端开发那些事儿，欢迎关注！
加载全部内容