Leetcode1-两数之和

---

---

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

让我们来分析一下题目：

已知：整数数组 nums、整数目标值 target

目的：找出和为目标值 target 的两个整数

要求：返回数组下标（索引）

---

示例

示例1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例2

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例3

输入：nums = [3,3], target = 6
输出：[0,1]

解析

暴力法

假如我们有如下数组[11,15,2,7]，并有一个目标值target=9，那么我们的目的就是在数组中找两个数，使其和为9。

我们可以先以“11”作为主要研究对象，数组中剩余的元素中寻找是否存在与11相加等于9的元素，怎么寻找呢？就是让剩余的每个元素与11相加，如果存在则返回其索引，同理，以“15”作为主要研究对象，但此时不再考虑15以前的元素11，因为以“11”为研究对象时，已经考虑过[11,15]的组合了，同理，以“2”、“7”作为主要研究对象.

要想让11与所有元素相加，可以先用一个定指针（红指针）放在11的位置，然后用一个动指针（蓝指针）分别指向剩余的元素，并将每次指针指向的元素与11相加，并判断是够等于9

当动指针遍历完剩余所有的元素，并没有发现相加等于9时，将定指针指向下一个元素15，并将动指针遍历15之后的剩余元素

同理，将定指针指向下一个元素2

当定指针指向“2”，动指针指向“7”时两数相加等于9，这个说明我们找到了这两个目标元素，此时我们需要返回两个元素的索引值[2， 3]

伪代码

我们分析完后，根据思想看一下伪代码

func(nums, target)——> []:
    result = []
    for i in [0, len(nums)]:
        for j in [i+1, len(nums)]:
            sum = nums[i] + nums[j]
            if sum == target:
                result[0] = i
                result[1] = j
                return result
1
2
3
4
5
6
7
8
9

首先是建立一个函数，输入的是数组和目标值，返回的时一个索引值数组

func(nums, target)——> []:
1

定义一个数组result，用来返回最后的索引值

result = []
1

设置两个指针，一个定指针i，和一个动指针j，分别for 循环遍历所有元素，并将两数相加

 for i in [0, len(nums)]:
        for j in [i+1, len(nums)]:
            sum = nums[i] + nums[j]
1
2
3

判断两数的和是否等于目标值target，如果等于目标值则返回两个数的索引值，其中result数组第一个值为定指针指向的位置i，第二个值为动指针指向的位置j

if sum == target:
                result[0] = i
                result[1] = j
                return result
1
2
3
4

python 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        for i in (0,len(nums)):
            for j in (i+1, len(nums)):
                sum = nums[i] + nums[j]
                if sum == target:
                    result = [i,j]
                    return result
1
2
3
4
5
6
7
8
9

哈希表

用哈希表的函数就是减少了算法的时间复杂度，例如当以“11”作为主要研究对象，遍历剩余所有元素时，时间复杂度为O（N），而用哈希表时，对于元素“11”，我们只需要找剩余的元素中有没有-2，因为11+（-2）=9，如果有则返回索引值，此时的时间复杂度为O（1）

将元素的值作为key，将元素的索引作为value

有了哈希表后，秩序遍历数组最终的元素，当遍历到11时，在哈希表中寻找是否有-2，当遍历到15时，在哈希表中寻找是否有-6，依次进行，直到找到和为9的两个元素。

伪代码

我们分析完后，根据思想看一下伪代码

func(nums, target)——>[]:
    result = []
    map = HashTable()
    for i in (0, len(nums)):
        map.add(nums[i], i)
    for j in (0, len(nums)):
        diff = target - nums[j]
        if (map.containsKey(diff) and map.get(diff) != j)
            result[0] = j
            result[1] = map.get(diff)
            return result
1
2
3
4
5
6
7
8
9
10
11

首先是建立一个函数，输入的是数组和目标值，返回的时一个索引值数组

func(nums, target)——> []:
1

定义一个数组result，用来返回最后的索引值

result = []
1

创建一个哈希表，并将所有元素放入哈希表中

    map = HashTable()
    for i in (0, len(nums)):
        map.add(nums[i], i)
1
2
3

遍历所有元素，并计算与该元素和等于9的元素

    for j in (0, len(nums)):
        diff = target - nums[j]
1
2

如果海西表中存在与该匀速加和等于9的元素，则返回两个元素的索引值

if (map.containsKey(diff) and map.get(diff) != j)
            result[0] = j
            result[1] = map.get(diff)
            return result
1
2
3
4

python 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        hashtable = {}
        for i,num in enumerate(nums):
            diff = target - num
            if diff in hashtable:
                result = [hashtable[diff], i]
                return result
            hashtable[nums[i]] = i
        return []
1
2
3
4
5
6
7
8
9
10
11