402v

最近在刷leetcode，对自己的算法思路做个简单的记录，希望最后回顾起来自己是有提高的。

通篇算法都是用Ruby语言实现，文内不再赘述。Markdown没有支持数学格式，所以时间复杂度的记法比较粗糙，见谅。

这一系列的文章可以在这里找到。

本期题目:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

Subscribe to see which companies asked this question

题目的意思是从一个整型数组中选出两个数字之和为指定的整数，要求返回这两个数字的位置（注意是从1开始的，即数组的下标加一）。为了描述方便，我们再举一个更为普遍的输入输出：

Input: numbers={2, 6, 3, 7, 11, 8, 15}, target=10

Output: index1=1, index2=6

本着多些时间可以少些Code的原则，仔细思考。

从第一个元素起和其他元素做一次相加与目标数字比较，最后返回找到的数字位置。最基本的思路就是这个，那么我们至少有了一种时间复杂度为n2的解法了；继续考虑下去先前已经比较过的元素就不需要再次比较，比如从左到右循环时2和6已经相加过，那么6和2就不需要比较了，这样下来算法时间复杂度稍好一些的算法。（数学真的不好，应该是x*(n-x)的连加，但不知道算出来是多少。。。）

基于上面的思路还可以做一些小的优化，但不会影响到算法的时间复杂度：

大于target的数不做比较 Coding后发现这个不能做，原因是integer可能是复数

重中之重：边界条件的考虑

数组为空，这里我们用 index1=0 || index2=0 表示没有找到这样的一对数
数组长度小于2

程序出口：因为原题假设每个输入中只有一组正确的值因此当我们找到这样一组值时直接跳出返回；或者外层循环到最后一个元素

返回值：一个包含index1和index2的元组，且index1小于index2

###开始Coding

第一次submit答案如下，显示Time Limit Exceeded

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    index1=0,index2=0
    
    if nums.length < 2 then return [index1, index2] end
        
    nums.each_index do |i|
        nums[i+1..nums.length].each_index do |j|
            if nums[i] + nums[j+i+1] == target then
                puts "first num: #{nums[i]} at index:#{i}, second num: #{nums[j+i+1]} at index:#{j+i+1}"
                return [i+1, j+i+2]
            end
        end
    end
    
    return [index1, index2]
end

显然算法时间复杂度太高不满足要求，那就只能再想其他的办法。优化有两个选择，都是已空间换时间的方式：

给当前数组排序（nlogn），然后用从两端（记为small、big）开始查找，之和大于target值则big减一，之和小于target值则small加一，直到之和等于target值或者small==big-1为止。时间复杂度为nlogn，空间复杂度为n；
利用Hash，Hash查找的时间复杂度为1，因此可以很好的做到以空间换取时间。具体做法是先循环一次以整型数组值为key，索引为value存储到hash中，这样之后我们通过值可以快速的拿出这个值的索引；接下来再循环一次尝试用target值减去当前值作为key，去hash中读取，如果能取到则说明当前这对值为期望值，他们的索引加一组成的数组，即为所求。

最终选择hash这种方式，代码如下：

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    ret = []
    
    return ret unless nums.length > 1
        
    hash = {}
    nums.each_index do |i|
        hash[nums[i]] = i
        #puts "cur hash:#{hash}"
    end
    
    nums.each_index do |i|
        
        #puts "return i:#{i} & #{target - nums[i]} & #{hash.has_key?(target - nums[i])}"
        if hash.has_key?(target - nums[i]) && i != hash[target - nums[i]] then
            return [i+1, hash[target - nums[i]]+1]
        end
    end
    
end

此文为第一篇。

LeetCode实战-Two Sum

评论 · 0