今天是双指针专题，双指针题目居多
lc167. 两数之和II - 输入有序数组（MD） 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers 按 非递减顺序 排列-1000 <= target <= 1000仅存在一个有效答案 利用好这道题数组 非递减顺序排列 的特性，可以使用双指针法，左右互推。如果求出来的两数之和偏大，右指针左移，偏小则左指针右移
class Solution { public int [] twoSum(int [] numbers, int target) { int l = 0 , r = numbers.length - 1 ; int [] res = new int [2 ]; while (l < r) { int sum = numbers[l] + numbers[r]; if (sum == target) { res[0 ] = l + 1 ; res[1 ] = r + 1 ; break ; } else if (sum < target) { l++; } else { r--; } } return res; } }
lc11. 盛最多水的容器（MD） 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
提示：
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4双指针经典题了
还是老样子，左右双指针。每次都要用max函数判定一下最大水量。至于移动，则优先移动高度最低的一边，毕竟我们都知道，木桶能装多少水取决于最短的边，而不是最长的边
class Solution { public int maxArea (int [] height) { int l = 0 , r = height.length - 1 ; int res = 0 ; while (l < r) { int water = (r - l) * Math.min(height[l], height[r]); res = Math.max(res, water); if (height[l] < height[r]) { l++; } else { r--; } } return res; } }
lc15. 三数之和（MD） 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5还是双指针
思路不复杂。最开始这个数组是乱序的，如果我们要用到双指针这个技巧，那么必须先做一个排序，让他变成升序的
根据题目nums[i] + nums[j] + nums[k] == 0 的要求，显然，如果此时我们遍历到的nums[i] 已经大于 0 了， 那么肯定没法让这个等式成立，所以可以直接break掉
介于本题中要求答案不能包含重复三元组，所以需要去重
然后就是双指针了，基本和其他题目的代码是一样的
接下来就是找到一个三元组之后的去重。因为前面提及不能包含重复三元组，所以在找到一个三元组之后我们必须通过判断l与l + 1、r与r - 1的值是否相等，完成去重操作
class Solution { public List<List<Integer>> threeSum (int [] nums) { List<List<Integer>> res = new ArrayList <>(); Arrays.sort(nums); for (int i = 0 ; i < nums.length; i++) { if (nums[i] > 0 ) { return res; } if (i >= 1 && nums[i - 1 ] == nums[i]) { continue ; } int l = i + 1 , r = nums.length - 1 ; while (l < r) { if (nums[i] + nums[l] + nums[r] > 0 ) { r--; } else if (nums[i] + nums[l] + nums[r] < 0 ) { l++; } else { res.add(Arrays.asList(nums[i], nums[l], nums[r])); while (l < r && nums[l] == nums[l + 1 ]) { l++; } while (l < r && nums[r] == nums[r - 1 ]) { r--; } r--; l++; } } } return res; } }
lc146. LRU缓存（MD） 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^5最多调用 2 * 10^5 次 get 和 put 伪装成Mid的Hard题，如果以前没有做过这道题，初见这道题还是非常有难度的，因为这道题要一次用到两个数据结构——哈希表和链表，并且要对这两个数据结构的增删改查操作非常非常熟悉
没什么好说的了，面试超高频算法题，背也要背下来
本质上就是看链表操作是否熟练，头插尾插头删尾删。这道题是不能使用语言本身自带的类似于 LinkedHashMap 这种集合的，要求自己手写链表，面试中同样要求全程手写链表，这就要求了我们对链表的结构和链表节点的添加/删除要足够的熟悉，所以不要试图蒙混过关
public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode () {} public DLinkedNode (int _key, int _value) { key = _key; value = _value; } } private Map<Integer, DLinkedNode> cache = new HashMap <>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache (int capacity) { this .size = 0 ; this .capacity = capacity; head = new DLinkedNode (); tail = new DLinkedNode (); head.next = tail; tail.prev = head; } public int get (int key) { DLinkedNode node = cache.get(key); if (node == null ) { return -1 ; } moveToHead(node); return node.value; } public void put (int key, int value) { DLinkedNode node = cache.get(key); if (node == null ) { DLinkedNode newNode = new DLinkedNode (key, value); cache.put(key, newNode); addToHead(newNode); size++; if (size > capacity) { DLinkedNode tail = removeTail(); cache.remove(tail.key); size--; } } else { node.value = value; moveToHead(node); } } private void addToHead (DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode (DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead (DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail () { DLinkedNode res = tail.prev; removeNode(res); return res; } }
