数据结构入门（第二天）

1. 两数之和

找出数组中两个数之和等于target的两数下标。

暴力枚举可以

但时间较长，时间复杂度$O(N^2)$

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: n = len(nums) for i in range(n): for j in range(i + 1, n): if nums[i] + nums[j] == target: return [i, j] return []

哈希表

官方题解的一个比较巧妙的方式：使用哈希表（字典） 用字典记录出现过的数字的位置。 时间复杂度$O(N)$，空间复杂度$O(N)$

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashtable = dict() for i, num in enumerate(nums): if target - num in hashtable: return [hashtable[target - num], i] hashtable[nums[i]] = i return []

88. 合并两个有序数组

两个有序数组，将第二个数组nums2合并到第一个数组nums1。

双指针

1.可以用双指针遍历两个数组：

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # 两个中存在空数组的时，直接返回 if m == 0: nums1[:] = nums2[:] return if n == 0: return index1,index2 = 0,0 t = [] while index1<m and index2<n: if nums1[index1] <= nums2[index2]: t.append(nums1[index1]) index1 += 1 else: t.append(nums2[index2]) index2 += 1 if index1 < m: t += nums1[index1:m] else: t += nums2[index2:n] nums1[:] = t[:]

官方版本，更简洁、清楚。

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ sorted = [] p1, p2 = 0, 0 while p1 < m or p2 < n: if p1 == m: sorted.append(nums2[p2]) p2 += 1 elif p2 == n: sorted.append(nums1[p1]) p1 += 1 elif nums1[p1] < nums2[p2]: sorted.append(nums1[p1]) p1 += 1 else: sorted.append(nums2[p2]) p2 += 1 nums1[:] = sorted

（暴力） 追加后排序

更简单粗暴的方式是直接将nums2追加到nums1后，进行排序。 及其简单而且效果很好。

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ nums1[m:] = nums2 nums1.sort()