LeetCode刷题解析：两数之和与两数相加

"LeetCode刷题笔记包含了四道经典的编程题目，分别是：两数之和、两数相加、无重复字符的最长子串和寻找两个有序数组的中位数。这些题目涉及到数组操作、哈希映射、链表处理以及数组排序等核心算法和数据结构知识。" 在LeetCode刷题笔记中，我们首先遇到了“两数之和”问题。这个问题要求在给定的整数数组`nums`中找到两个数，使得它们的和等于目标值`target`，并返回这两个数的数组下标。解答中采用了一种高效的方法，利用哈希映射`HashMap`来存储数组元素与它们的索引。遍历数组时，检查当前元素与目标值的差是否已存在于哈希表中，如果存在则直接返回这两个数的索引；否则，将目标值与当前元素的差值作为键，当前元素的索引作为值存入哈希表。这种方法的时间复杂度为O(n)，避免了双重循环，提高了效率。 接下来是“两数相加”的问题，这是一道涉及链表操作的题目。给定两个表示逆序存储的非负整数的链表，我们需要计算它们的和，并返回一个新的链表表示结果。解答中创建了一个新的链表`root`作为结果链表的头节点，然后用一个指针`cursor`遍历两个链表，同时维护一个进位变量`carry`。对于每个节点，我们计算两个节点的值加上进位的和，然后根据和的大小更新新链表的节点值和进位。最后，如果进位不为0，需要在结果链表末尾添加一个新的节点。这个方法同样保持了O(n)的时间复杂度，其中n是两个链表的总长度。 “无重复字符的最长子串”问题则考察了字符串处理和滑动窗口的概念。这道题要求找到给定字符串中不包含重复字符的最长子串的长度。解决此问题的一种常见方法是使用滑动窗口的思想，通过两个指针分别表示子串的开始和结束位置，同时使用哈希集合记录当前子串中的字符。每次移动结束指针时，检查新加入的字符是否已存在于哈希集合中，如果不存在则更新最长子串长度，否则将开始指针向右移动一位以移除一个字符。这种方法可以在O(n)的时间内完成。 最后，“寻找两个有序数组的中位数”题目需要在两个已排序的数组中找到中位数。如果数组元素总数是奇数，中位数是中间的数；如果是偶数，中位数是中间两个数的平均值。一种有效策略是采用二分查找法，通过比较两个数组中间元素的大小来逐步缩小搜索范围，直到找到满足条件的中位数。 这些题目都是算法和数据结构的基础练习，对于提升编程能力、理解和运用核心算法有极大的帮助。通过反复练习和深入理解，开发者可以更好地应对实际工作中遇到的各种复杂问题。