滑动窗口
3.无重复字符的最大子串
题目：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
思路：
滑动窗口思想，左右指针一直移动，遇到重复的就更新左边界(移除左边的元素)，数据结构方面用HashMap存储<当前字符,出现 的位置+1>
步骤：
定义数据结构
遍历字符串
遇到重复的就更新左边界（左指针）
更新最大长度
存当前字符对应的左边界
返回结果
代码
class Solution {
public int lengthOfLongestSubstring(String s) {
//滑动窗口 hashmap存储字符 以及字符对应的左边界
HashMap<Character,Integer> map = new HashMap<>();
int res = 0;
int last_next = 0;
//i右指针 j左指针
for(int i = 0,j = 0;i < s.length();i++){
//如果当前右指针的字符是出现过的
if(map.containsKey(s.charAt(i))){
//取一下这个字符的下一个字符下标 也就是左边界的起始位置
last_next = map.get(s.charAt(i));
//更新一下左指针
j = Math.max(j,last_next);
}
//更新一下最大长度
res = Math.max(res,i-j+1);
//存一下当前字符对应的下一次左边界的下标
map.put(s.charAt(i),i+1);
}
return res;
}
}链表
146.LRU缓存
题目：
请你设计并实现一个满足 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) 的平均时间复杂度运行。
思路：
首先我们需要一种数据结构来满足这道题的需求：遍历是O(1)复杂度，还能够记录使用顺序。
单是数组/链表/哈希表一种无法满足，使用LinkedHashMap又违反了这道题的初心，所以在选择数据结构上选择好了也就事半功倍了，我们选择的是双向链表（记录使用的顺序）+哈希表（查找O1），哈希表的key是Node的key，value是Node
然后在设计双向链表的时候有一点就是要使用哑节点，也就是真实的链表数据是在不变的head和tail之间的：
head (dummy) ↔ 实际节点1 ↔ 实际节点2 ↔ ... ↔ tail (dummy)
这样做的好处有两点：第一避免空指针判断，第二统一了头部插入和尾部删除操作
步骤：
定义数据结构Node类和LRUCache 类成员
初始化（哑节点）
完成get方法：判断node是否为空？返回-1：把node移到链表最前，返回node的value
完成put方法：判断node是否为空？不为空更新，然后将node移到链表最前；为空的话则创建新节点，把新节点移到链表最前，然后检查容量，如果超过链表容量，移除链表末尾的，并删除哈希表中的key
以上步骤需要四个方法完成：
addToHead(node) - 头部插入；插入的是新节点
removeNode(node) - 删除节点；
moveToHead(node) - 移到头部；把已有节点移到头部（调用2+1方法）
removeTail() - 删除尾部；获取尾部的节点，调用2方法
代码
class LRUCache {
//定义一个节点数据结构 双向链表+哈希表
class Node{
int key;
int value;
Node prev;
Node next;
Node(int key,int value){
this.key = key;
this.value = value;
}
}
private Map<Integer,Node> cache;
private int capacity;
private Node head,tail;
//双向链表技巧：哑节点
//head (dummy) ↔ 实际节点1 ↔ 实际节点2 ↔ ... ↔ tail (dummy)
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>();
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if(node == null){
return -1;
}
//使用后移动到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
//如果节点非null 更新值 然后移动到头部
if(node != null){
node.value = value;
moveToHead(node);
}else{
//如果节点是null 新建一个节点
Node newNode = new Node(key,value);
cache.put(key,newNode);
addToHead(newNode);
//检查容量
if(cache.size() > capacity){
Node tailNode = removeTail();
cache.remove(tailNode.key); //map自带remove方法
}
}
}
//将当前新来的节点移到最前
private void addToHead(Node node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
//移除节点
private void removeNode(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
//将当前已有节点移动到最前
private void moveToHead(Node node){
removeNode(node);
addToHead(node);
}
//删除并返回尾部的节点
private Node removeTail(){
Node res = tail.prev;
removeNode(res);
return res;
}
}