1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 10^3
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

import java.util.*;
public class twoSum {public static class Solution {public static int[] twoSum(int[] nums, int target) {Map cache = new HashMap<>();for (int i = 0; i < nums.length; i++) {int distance = target - nums[i];if (cache.containsKey(distance)) {return new int[] { cache.get(distance), i };} else {cache.put(nums[i], i);}}return new int[] {};}}public static void main(String[] args) {Solution s = new Solution();int nums[] = {2,7,11,5};int res[] = s.twoSum(nums, 9);for (int i = 0; i < res.length; i++) {System.out.print(res[i] + " ");}System.out.println();int nums2[] = {3,2,4};int res2[] = s.twoSum(nums2, 6);for (int i = 0; i < res2.length; i++) {System.out.print(res2[i] + " ");}System.out.println();int nums3[] = {3,3};int res3[] = s.twoSum(nums3, 6);for (int i = 0; i < res3.length; i++) {System.out.print(res3[i] + " ");}System.out.println();}
}

输出：

0 1
1 2
0 1

2. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

提示：

n = height.length
2 <= n <= 3 * 10^4
0 <= height[i] <= 3 * 10^4

代码：

import java.util.*;
public class maxArea {public static class Solution {public int maxArea(int[] height) {int N = height.length;int i = 0;int j = N - 1;int max = 0;while (i < j) {int c = (j - i) * Math.min(height[i], height[j]);if (c > max) {max = c;}if (height[i] > height[j]) {j--;} else {i++;}}return max;}}public static void main(String[] args) {Solution s = new Solution();int height[] = {1,8,6,2,5,4,8,3,7};System.out.println(s.maxArea(height));int height2[] = {1,1};System.out.println(s.maxArea(height2));int height3[] = {4,3,2,1,4};System.out.println(s.maxArea(height3));int height4[] = {1,2,1};System.out.println(s.maxArea(height4));}
}

输出：

49
1
16
2

3. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

代码：

class Solution {public ListNode reverseBetween(ListNode head, int m, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;for (int i = 1; i < m; i++) {pre = pre.next;}head = pre.next;for (int i = m; i < n; i++) {ListNode nex = head.next;head.next = nex.next;nex.next = pre.next;pre.next = nex;}return dummy.next;}
}

递归法：

class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1) {
return reverseN(head, right);
}
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
}
ListNode successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
successor = head.next;
return head;
}
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor;
return last;
}
}