美文网首页
算法面试题01 - 两数之和

算法面试题01 - 两数之和

作者: long弟弟 | 来源:发表于2023-08-17 13:42 被阅读0次

    实现一个算法,在一个无序整型数组中,找到两个数使其和为一个给定的值。请给出算法实现的代码,并分析算法时间和空间复杂度。

    【示例】
    给定数组numbers = [3, 7, 2, 5, 9],目标值sum = 9
    因为numbers[1] + numbers[2] = 7 + 2 = 9
    返回[1,2]

    【要求】
    输入一个无序数组,通过算法可以找到两数之和等于目标值的两元素的索引。

    答案:

    let numbers = [3, 7, 2, 5, 9]
    print(twoSum(numbers, 9))
    
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    
        var dict = [Int:Int]()
    
        for (index, num) in nums.enumerated() {
            let other = target - num
            if let storedIndex = dict[other] {
                return [storedIndex, index]
            } else {
                dict[num] = index
            }
        }
    
        return []
    }
    

    这个算法首先使用一个字典保存每个元素和其索引。然后遍历数组,并查找每个元素所对应的补数是否存在于字典中。
    时间复杂度为 O(n),其中 n 为数组长度。算法只需要遍历一次数组,并在字典中查找操作,所以时间复杂度为线性。
    空间复杂度为 O(n),因为使用了一个字典存放了数组中的每个元素。
    所以这个算法的时间和空间复杂度较优,总体来说效率较高。这是一种常见的两数之和问题的解法。

    知识点详解:

    无序整型数组指的是数组中的元素可以是任意顺序,不是排序后的顺序。
    例如:[3, 7, 2, 5, 9]
    这就是一个无序整型数组,数组中的整数元素并不是按照大小排序的。
    如果数组是:[2, 3, 5, 7, 9]
    则这是一个有序数组,元素是按照从小到大的顺序排列的。

    算法思路

    1. 定义一个字典dict来存放元素和索引
    2. 使用enumerated()遍历数组,同时获取元素和索引
    3. 定义other变量,来计算当前元素的补数(target值减去当前元素)
    4. 在字典中查找other是否存在:
      • 如果存在,表示找到了两数之和,直接返回两个元素的索引
      • 如果不存在,则将当前元素和索引添加到字典中
    5. 遍历完成如果未找到,返回空数组
    6. 时间复杂度为O(n),空间复杂度为O(n)
      这种利用字典保存元素和索引的方法,可以快速查找补数是否存在,从而得出两数之和的结果,是一个常用的算法

    算法执行过程:

    1. dict = {}
    2. num = 3,dict[3] = 0
    3. num = 7,dict[7] = 1
    4. num = 2,目标值9与当前num的差值是7,7已在dict中,返回[dict[7] , index],即返回[1, 2]
    5. 两数之和为7 + 2 = 9,索引分别为1和2,返回[1, 2]

    代码释义:

    func twoSum(_ nums: [Int], _ target: Int) -> [Int]
    
    • nums: 输入的整数数组,用于查找两数之和
    • target: 查找的目标和的值
    • 返回值:[Int]: 返回一个整数数组,包含两数之和的两个元素在原数组中的索引

    也就是说:

    • 输入:一个整数数组nums,和一个目标值target
    • 输出:一个整数数组,包含两个元素在nums数组中的索引,这两个元素相加等于target

    题外话

    如果题目中的无序数组换成有序数组,该如何优化呢?

    对于有序数组,可以利用二分查找算法来降低时间复杂度。
    具体思路是:

    1. 给定一个有序数组 nums 和目标值 target
    2. 对数组进行二分查找,找到一个数 num
    3. 计算目标值与 num 的差值 diff = target - num
    4. 再在数组中二分查找 diff
    5. 如果找到diff,返回 num 和 diff 的下标即可
    6. 如果未找到,移动 num 的查找范围,重复步骤2-5

    该算法的时间复杂度可以降低到 O(logn),比线性查找更快。

    参考代码:

    func twoSum2(_ nums: [Int], _ target: Int) -> [Int] {
    
        for i in 0..<nums.count {
            let complement = target - nums[i]
            if let j = binarySearch(nums, complement, i+1, nums.count-1) {
                return [i, j]
            }
        }
        
        return []
    }
    
    func binarySearch(_ nums: [Int], _ target: Int, _ left: Int, _ right: Int) -> Int? {
    
        if left > right {
            return nil
        }
        
        let mid = (left + right) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            return binarySearch(nums, target, mid+1, right)
        } else {
            return binarySearch(nums, target, left, mid-1)
        }
    }
    

    相关文章

      网友评论

          本文标题:算法面试题01 - 两数之和

          本文链接:https://www.haomeiwen.com/subject/jyalmdtx.html