算法面试题01 - 两数之和

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

【示例】
给定数组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)
    }
}