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
classSolution: deftwoSum(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.