算法面试高频题——两数之和、反转链表、LRU缓存

算法面试是 Java 后端面试的必过关卡。这篇从最高频的题目入手讲清思路、代码和复杂度。一、两数之和publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegermapnewHashMap();for(inti0;inums.length;i){intcomplementtarget-nums[i];if(map.containsKey(complement)){returnnewint[]{map.get(complement),i};}map.put(nums[i],i);}returnnewint[]{-1,-1};}二、反转链表publicListNodereverseList(ListNodehead){ListNodeprevnull;ListNodecurrhead;while(curr!null){ListNodenextcurr.next;curr.nextprev;prevcurr;currnext;}returnprev;}三、LRU 缓存classLRUCache{classNode{intkey,value;Nodeprev,next;Node(intk,intv){keyk;valuev;}}privateintcapacity;privateMapInteger,Nodemap;privateNodehead,tail;publicLRUCache(intcapacity){this.capacitycapacity;mapnewHashMap();headnewNode(0,0);tailnewNode(0,0);head.nexttail;tail.prevhead;}publicintget(intkey){Nodenodemap.get(key);if(nodenull)return-1;remove(node);addToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){Nodenodemap.get(key);if(node!null){node.valuevalue;remove(node);addToHead(node);return;}if(map.size()capacity){Nodelasttail.prev;remove(last);map.remove(last.key);}NodenewNodenewNode(key,value);addToHead(newNode);map.put(key,newNode);}privatevoidaddToHead(Nodenode){node.nexthead.next;node.prevhead;head.next.prevnode;head.nextnode;}privatevoidremove(Nodenode){node.prev.nextnode.next;node.next.prevnode.prev;}}复杂度分析题目时间空间核心思路两数之和O(n)O(n)哈希表存遍历过的值反转链表O(n)O(1)三个指针迭代LRU缓存O(1)O(n)双向链表哈希表 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。