LeetCode | 1. Two Sum 两数之和

发布于: 2020 年 06 月 02 日
LeetCode | 1. Two Sum 两数之和

写在前面:本文首发于 CSDN,由于本人比较中意 InfoQ 的写作平台,且该系列与 ARTS 相关,故搬运过来,后续关于 ARTS 的内容都会在 InfoQ 中做更新。

以下为原文搬运:

Two Sum 是 LeetCode 算法题库中的第一道题,难度为 Easy,题目地址为:https://leetcode.com/problems/two-sum/

1. 问题描述

给定一个整形数组和目标值,从数组中找出两个数,其和等于目标值,并输出这两个数的索引。

有两个假设:

  1. 输入的数组只有一个符合条件的解

  2. 数组中的元素不能使用两次

示例:

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 是注解返回值。

参考:

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

参考:

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

参考:

C#

通过 C# 来实现该算法时,涉及到的新知识点是:

  • Dictionary

在 C# 中,Dictionary 的主要用途是提供快速的基于键值的元素查找。Dictionary 的结构一般是这样的:Dictionary<[key], [value]>,它包含在System.Collections.Generic名空间中。

在使用 Dictionary 前,你必须对它的键类型和值类型进行声明。

Dictionary 的一些常用用法:

  1. 创建及初始化: var myDictionary = new Dictionary<int, string>();

  2. 添加元素: myDictionary.Add(1, "C#");

  3. 通过 Key 查找元素: myDictionary.ContainsKey(1))

  4. 通过 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 日 阅读数: 4
用户头像

Puran

关注

GIS从业者,正在往开发的路上小跑。 2018.03.29 加入

从业4年的GIS开发小白,work@esri。

评论

发布
暂无评论
LeetCode | 1. Two Sum 两数之和