leetcode回顾——Two Sum 快速找到两个数字之和等于目标值

LeetCode

今天做了一题Leetcode的题目，是数组类型的题目，题目很短，也很简单

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

这道题目就是让你在一个数组中找到两个数，这两个数的和必须等于目标值，如果采用暴力法，那么时间复杂度将会是O（N^2）级别。这会导致超时的结果。那么该如何做呢？如果把这个题目的两个未知数转为一个未知数，那么会不会更简单些呢？这是肯定的，两个未知数求一个数，倒不如利用结果和一个未知数，求另一个未知数。因此我们只需要利用减法操作就可以快速求解

我们利用目标值减去数组的每一个值，并判断差存不存在数组中，若存在，则就得到了答案；我们利用python的字典数据结构来作为中间存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: list[int]
        :type target: int
        :rtype: list[int]
        """
        hash = {}
        for i in range(len(nums)):
            if target - nums[i] in hash:
                return [hash[target - nums[i]], i]
            hash[nums[i]] = i
        return [-1, -1]


if __name__ == '__main__':
    s = Solution()
    print s.twoSum([3, 3], 6)

这是其中一种最快的方法，还有一种方法的时间复杂度是O（NlogN）级别的，这个方法的时间开销主要在于排序操作：

我们将数组进行排序操作，得到从小到大的序列，然后从数组最左边和最右边进行两个数的相加，如果大于目标值，我们把右边指向的位置向左移动一位，如果小于目标值，我们就把左边指向的位置向右移动一位；但是，这个方法由于排序了，势必将原先的顺序打乱，因此我们还需要利用一个方法记住原先的位置信息，可以利用一个数据结构来存储，也可以利用中间量复制一份数组，在复制的数组进行排序操作，再来获取原先数据的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: list[int]
        :type target: int
        :rtype: list[int]
        """
        tmp_nums = [i for i in nums]
        tmp_nums.sort()
        max_loc = len(nums) - 1
        for i in range(len(tmp_nums)):
            if tmp_nums[i] >= target:
                max_loc = i
                break
        l, r = 0, max_loc
        while l > r:
            ans = tmp_nums[l] + tmp_nums[r]
            if ans == target:
                break
            elif ans > target:
                r -= 1
            else:
                l += 1
        l = nums.index(tmp_nums[l])
        nums[l] = -1
        r = nums.index(tmp_nums[r])
        return [nums.index(tmp_nums[l]), nums.index(tmp_nums[r])]


if __name__ == '__main__':
    s = Solution()
    print s.twoSum([3, 3], 6)