Two Sum

题目介绍

LeetCode 1. Two Sum，题目的意思简单来说就是给 Target，从数组中找到两个数和，同一个数不可以用两次，且我在测试的时候发现会有同一个值出现两次的情况。

解题方法

暴力求解

很简单的方式，两个 for loop 就能解决，时间复杂度为 O(n²)。

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

散列表

散列表，Table Hash。这边只是很简单的应用，后续会介绍更加复杂的应用。简单的思想就是将数组中的数不断的读入，key - 是数组中的值，value - 是遍历数组的 index。写入的时候先判断 Target - nums[i] 的 key 是否存在 value。如果存在说明这个数已经被写入了，那么就找到了这两个数；如果不存在则写入数组。算法如下：

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dictionary = [Int: Int]()

        for i in 0..<nums.count {
            if let item = dictionary[target - nums[i]] {
                return [item, i]
            }
            dictionary[nums[i]] = i
        }

        return []
    }
}

PS: 本来没打算写这篇博客，主要是我朋友在写这一条的写了 Python 算法，如下：

import copy
def two_sum(nums, target):
    for index, item in enumerate(nums):
            a = target - item
            list = copy.copy(nums)
            del list[index]
            if a in list:
                if nums.index(a) == index:
                    return [index,list.index(a)+1]
                return [index, nums.index(a)]

简单的来看，是读取一个数首先删除本身，然后去判断 target - item 是不是存在数组中。我开始很疑惑，在没有使用散列表的情况下，只用数组解出来一定是牺牲了时空复杂度。果然问题在 if a in list:，python 的语法糖在做这句话的时候，其实是做了 For loop，所以时间复杂度为 O(n²)。迷惑了我朋友很久才想通的问题，大家在刷题的时候一定要注意：高级语言的语法糖和数据结构在带来遍历的同时，在处理方式上面可能会存在你不知道的时空耗费。

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/10/09/TwoSum/