1.两数之和（1 - 易）
题目描述：给定一个整数数组 nums 和一个整数目标值 target，在该数组中找出 和为目标值 的那 两个 整数，返回它们的数组下标。
示例 :
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
思路：本题可以多解法，但是核心考察点为哈希表，即建立值与索引的映射值，遍历数组获取结果。
代码实现：
public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])) { return new int[] {map.get(target - nums[i]), i}; } map.put(nums[i], i); } return null; }
2.两数之和II（167 - 易）
题目描述：给定数组升序，下标从1开始。
示例 :
输入：numbers = [2,3,4], target = 6 输出：[1,3]
思路：本题可以使用哈希表，但是数组严格升序。利用这一性质，可以定义双指针，遍历数组比较大小。
注意：不能使用二分查找，因为最终结果可能分别分布在两个区间。
代码实现：
public int[] twoSum(int[] numbers, int target) { int left = 0, right = numbers.length - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { break; } } return new int[] {left + 1, right + 1}; }
3.两数之和IV（653 - 易）
题目描述：判断二叉搜索树是否有两个元素的和为目标值。
示例 :
输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 输出: True
思路：
法1：直接递归遍历二叉搜索树，利用set存储节点，判断是否出现k - root.val。
法2：利用bst中序升序，双指针求解，如167题。
代码实现：直接遍历
private Set<Integer> set = new HashSet<>(); public boolean findTarget(TreeNode root, int k) { if (root == null) return false; if (set.contains(k - root.val)) return true; set.add(root.val); return findTarget(root.left, k) || findTarget(root.right, k); }
4.两整数之和（371 - 中）
题目描述：不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 :
输入: a = 1, b = 2 输出: 3
思路：位运算模拟两数相加（可自行举例）：可以递归或者迭代实现。
- 按位计算二进制相加（不算进位），相当于二进制按位异或操作。
- 计算进位值，相当于两个数按位与，再进行左移
- 重复上述操作直到进位值b为0，得到累加和a。
代码实现：
public int getSum(int a, int b) { while (b != 0) { int tmp = a ^ b; b = (a & b) << 1; a = tmp; } return a; // 递归实现 return b == 0 ? a : getSum(a ^ b, (a & b) << 1); }
5.两数相加（2 - 中）
题目描述：按照链表逆序形式存储的两个数进行加和，以相同的形式返回结果。数字不含前导0。
示例 :
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
思路：使用迭代模拟两数相加的过程：
- 先计算两节点值加和
sumVal，注意：加上上一轮的进位值 - 记录进位值
carry - 建立结果链表并连接
- 更新索引值，包括结果链表、
l1和l2
代码实现：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode cur = dummyHead; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int sum = carry; sum += l1 == null ? 0 : l1.val; sum += l2 == null ? 0 : l2.val; carry = sum / 10; ListNode sumNode = new ListNode(sum % 10); cur.next = sumNode; cur = sumNode; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } return dummyHead.next; }
6.两数相加II（445 - 中）
题目描述：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。要求：不修改链表。
示例 :
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7
思路：本题关键使用两个栈实现逆序取出链表的元素进行相加，剩下的解题思路与上题类似。
注意：我们最后返回的结果也是按照正序进行连接的，所以链表要进行倒序连接。
代码实现：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); while (l1 != null) { stack1.push(l1.val); l1 = l1.next; } while (l2 != null) { stack2.push(l2.val); l2 = l2.next; } int carry = 0; ListNode head = null; while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) { int sum = carry; sum += (stack1.isEmpty()) ? 0 : stack1.pop(); sum += (stack2.isEmpty()) ? 0 : stack2.pop(); ListNode node = new ListNode(sum % 10); node.next = head; head = node; carry = sum / 10; } return head; }
7.两数相加II（445 - 中）
题目描述：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。要求：不修改链表。
示例 :
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7
思路：本题关键使用两个栈实现逆序取出链表的元素进行相加，剩下的解题思路与上题类似。
注意：我们最后返回的结果也是按照正序进行连接的，所以链表要进行倒序连接。
代码实现：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); while (l1 != null) { stack1.push(l1.val); l1 = l1.next; } while (l2 != null) { stack2.push(l2.val); l2 = l2.next; } int carry = 0; ListNode head = null; while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) { int sum = carry; sum += (stack1.isEmpty()) ? 0 : stack1.pop(); sum += (stack2.isEmpty()) ? 0 : stack2.pop(); ListNode node = new ListNode(sum % 10); node.next = head; head = node; carry = sum / 10; } return head; }
