十分钟搞定Google面试题:返回数组任意两个数之和等于给定数值k

原创
2020/04/29 17:03
阅读数 338

问题

给定一个数字数组和一个数字k,返回数组中是否有两个数字加起来等于k。

例如,给定数组:[10、15、3、7],和k:17,因为10 + 7为17,所以返回true。

这个问题大概是在2018年出现在Google的面试题里。 建议在往下阅读之前,自己先动手解题。

解题分析

  1. 初始化一个空的哈希表: s。
  2. 遍历数组A[]里的每个元素A[i],并执行如下操作:
    1. 如果集合包含:给定数字k-元素A[i],就返回true。
    2. 否则把元素A[i]添加到哈希表里,等待下次迭代。

这个问题用哈希技术来更高效的解决,利用哈希表来检查数组 A[] 当前值 A[i] ,即如果 ( k - A[i] )  的结果在哈希表里,说明数组里包含有:A[i]、( k - A[i] ),如果没检查出来,就继续遍历数组。

更加形象的描述:遍历数组[10、15、3、7],判断(给定数字17-当前值10)的值:7,是否存在哈希表map里,如果7不存在map里,我们就把10放进map里,此时map:{10},然后继续遍历数组,遍历到了7,此时map:{10,15,3},我们再用17-7=10,判断10是否在哈希表map里,当然是在了!

数组[10、15、3、7]:

遍历数组第1次:

 遍历数组第4次:

算法复杂度分析 

  • 时间复杂度分析: O(n)
    最坏的情况是整个数组只需要遍历一次。
  • 空间复杂度分析: O(n)
    最快的情况是数组每个元素都需要放进哈希表里。

用JavaScript来解题

首先,写一个名为“ifContains”的函数,它接受两个参数(数组、给定数字k)并返回一个布尔值(true - false)。

function ifContains(list_of_numbers, target) {
    return false
}

接下来,我们声明一个空的set变量来保存临时值。(set是js里没有重复值的集合)

var cache = new Set()

然后,我们循环访问数组中的每个元素。

for (let i = 0; i < list_of_numbers.length; i++) {
}

我们需要判断cache set是否包含给定数值k减去当前项的结果数,如果cache set不包含这个值,我们保存它并继续使用其他元素,否则返回true。

if (cache.has(target - list_of_numbers[i])) {
    return true
} 
cache.add(list_of_numbers[i])

如果不匹配任何元素,则返回false值。

return false

整体代码:

function ifContains(list_of_numbers, target) {
    var cache = new Set()
    for (let i = 0; i < list_of_numbers.length; i++) {
        if (cache.has(target - list_of_numbers[i])) {
            return true
        } 
        cache.add(list_of_numbers[i])
    }
    return false
}

var test_list = [10, 15, 3, 7]
var k = 17;
ifContains(test_list ,k)

F12打开chrome浏览器的console控制台,把整体代码粘贴到输入块,然后Enter确认,就能看到结果了。

结果是:true

总结

以上关于Google面试题“返回数组任意两个数之和等于给定数值k”的解题方案,你有没有更优的方案呢?

展开阅读全文
打赏
0
0 收藏
分享
加载中
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部