LeetCode 精选 TOP 面试题：两数之和与两数相加

LeetCode 精选 TOP 面试题（1）包括两道题目：1. 两数之和和2. 两数相加。第一道题目是关于在一个数组中找到两个数的和等于给定目标值的下标，可以通过暴力枚举或者使用哈希表的方法来解决。第二道题目是关于对两个链表表示的数字进行相加，模拟竖式加法的过程，从最低位到最高位逐位相加，如果和大于等于10则保留个位数字，并向前一位进1，最终得到结果。 在解决两数之和这道题目时，可以使用暴力枚举的方法。即通过两重循环枚举数组中的下标i和j，然后判断nums[i]和nums[j]是否等于给定的目标值target。这种方法的时间复杂度较高，为O(n^2)。 另一种解决两数之和的方法是使用哈希表。在C++中可以使用unordered_map<int, int> hash来存储前面遍历过的数，当枚举到当前数时，如果哈希表中存在target-nums[i]的元素，则表示已经找到符合条件的两个数。若不存在target-nums[i]的元素则继续枚举当前数，并将当前数放进哈希表中。这种方法只需扫描一遍数组，时间复杂度为O(n)。 在解决两数相加这道题目时，可以采用模拟的方法。即模拟竖式加法的过程，从最低位到最高位逐位相加，如果和大于等于10则保留个位数字，并向前一位进1。如果最高位有进位，则需在最前面补1。 具体实现时，可以同时从头开始枚举两个链表，将l1和l2指针指向的元素相加存到t中，再将t%10的元素存到dummy链表中，再t/10去掉存进去的元素，l1和l2指针分别指向下一个元素。当两个链表遍历完毕后，若最高位有进位，则需在最前面补1。这种方法模拟了竖式加法的过程，时间复杂度为O(max(m, n))，m和n分别表示两个链表的长度。 因此，LeetCode 精选 TOP 面试题（1）中的两道题目分别涉及了在数组中找到两个数的和等于给定目标值的下标，以及对两个链表表示的数字进行相加的模拟过程。不同的解决方法包括暴力枚举和哈希表的方法，以及模拟竖式加法的过程。这些方法各具特点，可以根据具体情况选择合适的方法来解决问题。