[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:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
分析
本题似乎很容易,遍历数组计算 nums[i] + nums[j] == target
即可,时间复杂度 $$\mathcal{O}(n^2)$$,空间复杂度为 $$\mathcal{O}(1)$$。
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;
}
结果
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
是否在数组中,需要对数组进行一轮遍历,时间复杂度为 $$\mathcal{O}(n)$$。如果能够更快速判断 x
是否在数组中,就可以缩短时间。我们可以通过空间换时间的方式,建立一个双向映射表,查表的时间开销为 $$\mathcal{O}(1)$$,极端情况下为 $$\mathcal{O}(n)$$,遍历数组的时间复杂度为 $$\mathcal{O}(n)$$,则可得到整体上的时间复杂度为 $$\mathcal{O}(n)$$,空间复杂度为 $$\mathcal{O}(n)$$。
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
结果
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.
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭