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

"这篇刷题笔记主要涵盖了LeetCode上的三道经典问题：两数之和、两数相加以及寻找两个有序数组的中位数。文章通过实例解析和代码实现来详细阐述解题思路和方法。" 在LeetCode的算法挑战中，"两数之和"是一个基础但重要的问题。给定一个整数数组`nums`和一个目标值`target`，我们需要找到数组中两个数，使得它们的和等于`target`。关键在于，每个数只能使用一次，因此不能简单地使用两重循环。这个问题可以通过哈希映射来解决。 解答如下： ```java private static int[] twoSum(int[] nums, int target) { int[] indexs = new int[2]; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { indexs[0] = i; indexs[1] = map.get(nums[i]); return indexs; } map.put(target - nums[i], i); } return indexs; } ``` 分析这个解决方案，我们首先创建一个长度为2的数组`indexs`用于存储结果下标，以及一个HashMap`map`来存储数组元素及其索引。在遍历数组的过程中，检查当前元素是否已存在于HashMap中，如果存在，说明已经找到了匹配的数，返回下标；否则，将目标值与当前元素的差值作为键，当前元素的索引作为值存入HashMap。这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。 另一道题目是"两数相加"，它要求我们将两个用链表表示的逆序存储的非负整数相加。链表节点只存储单个数字，且不以0开头。这个问题可以通过模拟加法运算的过程来解决，同时处理进位。 解答如下： ```java private ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode root = new ListNode(0); ListNode cursor = root; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int l1Val = l1 != null ? l1.val : 0; int l2Val = l2 != null ? l2.val : 0; int sum = l1Val + l2Val + carry; carry = sum / 10; cursor.next = new ListNode(sum % 10); cursor = cursor.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } return root.next; } ``` 在这个解法中，我们创建一个新的链表`root`，并初始化一个进位变量`carry`。然后，我们在循环中逐步处理两个链表的每个节点，计算当前位的和，更新进位，创建新节点并将其添加到结果链表中。当两个输入链表都遍历完并且没有进位时，返回结果链表的下一个节点（即跳过起始的0节点）。 这些题目旨在训练程序员的数据结构操作技巧和逻辑思维能力，是提升算法水平的绝佳实践。通过不断练习和理解，可以在面对类似问题时快速找到高效解决方案。