题解 | #不重复打印排序数组中相加和为给定值的所有二元组#

struct DLinkedNode{
//key 和 value
int key,value;
//双向指针
DLinkedNode* prev;
DLinkedNode* next;
//构造函数
DLinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}
DLinkedNode( int _key, int _value ):key(_key),value(_value),prev(nullptr),next(nullptr){}
};
class Solution {
unordered_map<int, DLinkedNode> cache;
DLinkedNode head;
DLinkedNode* tail;
int size=0;
int capacity=0;
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> LRU(vector<vector<int> >& operators, int k) {
// write code here
capacity = k;
if(capacity<0) return{};
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
if( !operators.size() )return {};
vector<int> res;</int></int></int>

    for( vector<int> op: operators ){
        if( op[0]==1 ){//执行set 
            set(op[1],op[2]);
        }else if(op[0] == 2){
            int value = get(op[1]);
            res.push_back(value);
        }
    }
    return res;

}
void set(int key, int value){
    if( !cache.count(key) ){//表中没有，则添加
        DLinkedNode* node = new DLinkedNode(key,value);
        cache[key] = node;//给哈希表添加key的value
        addToHead(node);
        if( ++size > capacity ){//超出范围
            //移除最后一个节点
            DLinkedNode * removed = removeTail();
            cache.erase(removed->key);
            delete removed;
            --size;
        }
    }else{//表中存在，更新到头部即可
        DLinkedNode* node = cache[key];
        node->value = value;
        moveToHead(node);
    }
}
int get(int key){
    if(!cache.count(key)) return-1;
    //存在key
    DLinkedNode* node = cache[key];
    moveToHead(node);
    return node->value;
}

void addToHead(DLinkedNode* node){
    node->prev = head;
    node->next = head->next;
    head->next->prev = node;
    head->next = node;
}

void removeNode(DLinkedNode* node){
    node->prev->next = node->next;
    node->next->prev = node->prev;
}
void moveToHead(DLinkedNode* node){
    removeNode(node);
    addToHead(node);
}

DLinkedNode * removeTail(){
    DLinkedNode* node = tail->prev;
    removeNode(node);
    return node;
}

};