LeetCode | 1. Two Sum 两数之和

关注
发布于: 2020 年 06 月 02 日
写在前面：本文首发于 CSDN，由于本人比较中意 InfoQ 的写作平台，且该系列与 ARTS 相关，故搬运过来，后续关于 ARTS 的内容都会在 InfoQ 中做更新。
﻿
以下为原文搬运：
﻿
Two Sum 是 LeetCode 算法题库中的第一道题，难度为 Easy，题目地址为：https://leetcode.com/problems/two-sum/
﻿
1. 问题描述给定一个整形数组和目标值，从数组中找出两个数，其和等于目标值，并输出这两个数的索引。
有两个假设：
输入的数组只有一个符合条件的解
数组中的元素不能使用两次
﻿
示例：
Given nums = [2, 7, 11, 15], target = 9,
﻿
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
2. 解题思路本题主要有两种方法：暴力（brute force）和映射（hash map）
暴力解法：通过两层循环遍历数组以得到所有的组合，将组合数与目标值进行对比，若相同则结束循环（因为假设1的存在）
映射：通过增加一个映射表以将循环缩减至一层。遍历数组中的元素，通过目标值与元素的差值与映射表中记录的元素进行对比，若符合则结束循环。
3. 知识点我是采用了两种编程语言来实现该算法，下面分别来记录我的一些收获。
﻿
Python通过 Python 来实现该算法时，有三个新知识点：
函数注解 Function Annotations
Map 函数
Enumerate 函数
﻿
函数注解 Function Annotations函数注解是PEP 3107 引入的语法，只能应用于 Python 3 中。函数注解可以让你在定义函数时，对参数和返回值添加注解。
﻿
def foobar(a: int, b: 'it's b', c: str = 5) -> tuple:
return a, b, c
a: int 这种是注解参数
c: str = 5 是注解有默认值的参数
-> tuple 是注解返回值。
﻿
参考：
基于 Python 3 新增的函数注解（Function Annotations ）语法实现参数类型检查功能 - Huang Huang 的博客
https://www.geeksforgeeks.org/function-annotations-python/
﻿
Map函数map() 会根据提供的函数对指定序列做映射。
第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表，在 Python 3 中是返回迭代器。
语法为：map (function, iteration, ...)
﻿
代码示例：
# Return double of n 
def addition(n): 
    return n + n 
  
# We double all numbers using map() 
numbers = (1, 2, 3, 4) 
result = map(addition, numbers) 
print(list(result)) 
输出为：2, 4, 6, 8
﻿
参考：
https://www.geeksforgeeks.org/python-map-function/
https://www.runoob.com/python/python-func-map.html
﻿
Enumerate 函数enumerate()是用来遍历一个可迭代容器(如列表、元组或字符串)中的元素，同时通过一个计数器变量记录当前元素所对应的索引值。
enumerate()语法：enumerate(sequence, [start=0])，其中 start 为下标起始位置。返回枚举对象。
﻿
通过enumerate()，你不再需要在 Python 代码中专门去生成元素索引，而是将所有这些工作都交给enumerate()函数处理即可。
﻿
示例：
names = ['Bob', 'Alice', 'Guido']
for index, value in enumerate(names, 1):
    print(f'{index}: {value}')
这段代码会输入如下内容：
1: Bob
2: Alice
3: Guido
﻿
参考：
译Python的enumerate()函数揭秘 - Hi,I’m Vimiix
https://www.runoob.com/python/python-func-enumerate.html
﻿
C#通过 C# 来实现该算法时，涉及到的新知识点是：
Dictionary
﻿
在 C# 中，Dictionary 的主要用途是提供快速的基于键值的元素查找。Dictionary 的结构一般是这样的：Dictionary<[key], [value]>，它包含在System.Collections.Generic名空间中。
在使用 Dictionary 前，你必须对它的键类型和值类型进行声明。 
﻿
Dictionary 的一些常用用法：
创建及初始化: var myDictionary = new Dictionary<int, string>();
添加元素: myDictionary.Add(1, "C#");
通过 Key 查找元素: myDictionary.ContainsKey(1))
通过 KeyValuePair 遍历元素：foreach(KeyValuePair<int, string> kvp in myDictionary)
﻿
参考：https://www.w3cschool.cn/csharp/csharp-86c42por.html
4. 代码在刚开始解该算法题时，完全不知道如何下手，在代码实现过程中，也是参考了 LeetCode 中的 Solution 及社区的一些讨论。这里把提交的代码列出来，作为参考。
Python实现两层循环：
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(length):
            for j in range(i+1, length, 1):
                if (nums[i] + nums[j] == target):
                    return [i, j]
                    break
﻿
通过 Python 的字典，且把加法变为减法来进行优化，其中关键点在dict_map = {}和for i, num in enumerate(nums):：
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict_map = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in dict_map:
                return [dict_map[diff], i]
            dict_map[num] = i
从 Runtime 运行时间，能明显感受到第二种算法的优势。
C# 实现两层循环：
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.GetLength(0); i++)
        {
            for (int j = i+1; j < nums.GetLength(0); j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    result[0] = i;
                    result[1] = j;
                    break;
                }
            }
        }
        return result;
    }
}
﻿
通过 Dictionary 来进行优化：
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var dict_map = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            int diff = target - nums[i];
            if (dict_map.ContainsKey(diff))
            {
                return new int[] {dict_map[diff], i};
                break;
            }
            else if (!dict_map.ContainsKey(nums[i]))
            {
                dict_map.Add(nums[i], i);
            }
        }
        return null;
    }
}
从 Runtime 运行时间，相比 Python 来说，第二种算法的优势不是很大。
﻿
发布于: 2020 年 06 月 02 日阅读数: 59
原文链接:【http://xie.infoq.cn/article/af6f2a93c9adc147a82c76229】。文章转载请联系作者。
Puran

关注
GIS从业者，正在往开发的路上小跑。 2018.03.29 加入
从业4年的GIS开发小白，work@esri。
发布
暂无评论
创作场景

LeetCode | 1. Two Sum 两数之和

1. 问题描述

2. 解题思路

3. 知识点

Python

函数注解 Function Annotations

Map函数

Enumerate 函数

C#

4. 代码

Python实现

C# 实现

Puran

评论
