前端学习算法3：一道来自头条的面试题

你的名字 2022-03-16 12:08 201阅读 0赞

朋友去面试头条的前端，二面，第一个题目，就是下面这张纸，面试官也会给一张纸要求手写答案。如果你看到就立刻知道了怎么解答，那可以直接忽略本文了，或者有更好的写法，直接评论区留言吧，谢谢~

> 我的学习风格总是想着循序渐进，下面从几个小题开始。

### 1 简单题目热身（简单场景递归一下） ###

> 题目:给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们组成的数组。 你不能重复利用这个数组中同样的元素。

> 其实就是一个数组，找出两个元素，他们的和是指定的值，但是不能一直就一个元素，也就是说加数组只有4的话，不能返回结果是\[4,4\]这样

> 运行结果如下

> 代码很简单，也不用什么解释吧。不过要引出来的是下面一种解法，递归。

var nums = [8, 9, 2, 15, 7, 1]
    var target = 9
    
    var twoSum = function(nums, target) {
    	var result = []
    
    	var _sum = function(nums, target){
    	    if(nums.length === 0){
    		return false
    	    }
                for(var i = 1; i < nums.length; i++){
           		    if((nums[0] + nums[i]) === target){
    	    		    result.push([nums[0] , nums[i]])
    	    	    }
           	    }
           	    nums.splice(0,1) // 或者使用 nums.shift()，删除数组第一个元素
           	    return _sum(nums, target)
    	 }
    	_sum(nums, target)
    	return result
    }
    console.log( twoSum(nums, target) )
    复制代码

> 运行结果如下，当然，和上述结果是一样的

> 小结 代码稍微多了一点，其实思想是一样的，不过想更好的解释递归，那么需要再把题目简化一下

> 题目：还是上面的题目，加上一个限定条件：你可以假设每种输入只会对应一个答案。也就是说对应这样的题干数组\[11, 7, 10, 2\] 只有 \[7,2\]这样一个结果。对于只有一个结果这样的情况，递归的写法代码会简练的多。

var twoSum = function(nums, target) {
        // 1
        var result = []
        if(nums.length === 0){
            // 2
            return false
        }
        for(var i = 1; i < nums.length; i++){
            if((nums[0] + nums[i]) === target){
        	    result.push([nums[0], nums[i]])
        	    // 3
        	    return result
        	}
        }
        // 4
        nums.shift()
        // 5
        return twoSum(nums, target)
    }
    console.log( twoSum(nums, target) )
    复制代码

> 小结 ：注释1 中，会把result置为\[\], 那岂不是每次递归调用这个方法时候，开始都是重置？答，因为前提条件已经改了，我们返回的结果只有一个 注释4 ，修改递归执行函数的参数，毕竟要每次不一样嘛要不然怎么进行下去。

> 提问，真的清楚每个 return 的作用吗？比如 注释5 那里的return不写的话，有什么区别？这个一定要清楚。

### 2 题目进阶（for循环？递归？） ###

> 根据上面例子，很容易想到3重循环，确实也是可以解决的，只是那个判定条件，有些low 并且假如是寻找长度为4子数组呢？那要for循环4次？显然不可取

### 3 回归主题（重点理解递归时候的return） ###

> 提问 ，如果用递归，这个问题怎么解决？

> 运行结果如下

#### 解析代码 ####

*  第一次执行 backTrace

1.  执行 backTrace(index, target) 方法index为0 target为9
2.  backTrace方法中，有三个终止条件，在第一次执行时候，这三个return没有一个会执行
3.  此时 buffer 为 \[2\]

*  第二次执行 backTrace

1.  执行 backTrace(index, target) 方法index为1 target为7
2.  三个return没有执行
3.  此时 buffer 为 \[2,3\]