神楽坂雪紀的投研笔记

呐、现在可以和你见面吗?我、等着你哟......

0%

【LeetCode】【0001】Two Sum

描述

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:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析

本题似乎很容易,遍历数组计算 nums[i] + nums[j] == target 即可,时间复杂度 ,空间复杂度为

1
2
3
4
5
6
7
8
9
10
int* twoSum(int* nums, int numsSize, int target) {
int *pos = malloc(sizeof(int) * 2);
for (pos[0] = 0; pos[0] < numsSize; pos[0]++) {
for (pos[1] = pos[0]+1; pos[1] < numsSize; pos[1]++) {
if (nums[pos[0]] + nums[pos[1]] == target)
return pos;
}
}
return pos;
}

结果

1
2
Runtime: 136 ms, faster than 42.35% of C online submissions for Two Sum.
Memory Usage: 7.7 MB, less than 42.92% of C online submissions for Two Sum.

优化

在第一种方法中,判断 target - nums[i] == x 得到的 x 是否在数组中,需要对数组进行一轮遍历,时间复杂度为 。如果能够更快速判断 x 是否在数组中,就可以缩短时间。我们可以通过空间换时间的方式,建立一个双向映射表,查表的时间开销为 ,极端情况下为 ,遍历数组的时间复杂度为 ,则可得到整体上的时间复杂度为 ,空间复杂度为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = dict()
nums_bidict = dict()
it = 0
nums_size = len(nums)
while it < nums_size:
nums_dict[it] = nums[it]
nums_bidict[nums[it]] = it
it += 1
it = 0
values = set(nums)
while it < nums_size:
ret = target - nums_dict[it]
if ret in values and it != nums_bidict[ret]:
return [it, nums_bidict[ret]]
it += 1

结果

1
2
Runtime: 44 ms, faster than 61.65% of Python3 online submissions for Two Sum.
Memory Usage: 15.9 MB, less than 5.08% of Python3 online submissions for Two Sum.