Java 高频算法面试题及详细答案（真实面试版）

Java高频算法面试题及详细答案（真实面试版）本套题库为互联网大厂高频手撕算法题，覆盖初级、中级Java开发面试核心考点，剔除套路化模板解析，全部采用工程化解题思路，代码可直接运行，解析贴合面试答题逻辑。一、数组与双指针（面试必考）1.两数之和（LeetCode1）题目描述：给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，且数组中同一个元素不能使用两遍。解题思路：优先使用哈希表解题。遍历数组，每遍历一个元素，计算需要匹配的目标差值，判断哈希表中是否存在该差值。存在则直接返回下标，不存在则将当前元素和下标存入哈希表。时间复杂度O(n)，优于暴力双重循环的O(n²)。java

importjava.util.HashMap;

importjava.util.Map;

publicclassTwoSum{

publicint[]twoSum(int[]nums,inttarget){

//key：数组元素，value：元素下标

Map<Integer,Integer>map=newHashMap<>();

for(inti=0;i<nums.length;i++){

intdiff=target-nums[i];

//找到匹配值，直接返回结果

if(map.containsKey(diff)){

returnnewint[]{map.get(diff),i};

}

//未找到，存入当前元素

map.put(nums[i],i);

}

//题目保证有唯一解，此处仅为语法兜底

returnnewint[]{};

}

}答案解析：遍历过程中单次查询哈希表时间为O(1)，整体线性遍历数组，效率极高。面试中需要对比暴力解法和哈希解法的优劣，重点说明空间换时间的核心思想。该题是算法面试入门必考，主要考察候选人对哈希表特性的理解。2.移除元素（LeetCode27）题目描述：给你一个数组nums和一个值val，需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，必须仅使用O(1)额外空间并原地修改输入数组。解题思路：快慢双指针解法。慢指针记录有效元素的位置，快指针遍历所有元素。快指针遍历到不等于val的元素时，将快指针元素赋值给慢指针位置，同时慢指针后移。最终慢指针的值即为新数组长度。java

publicclassRemoveElement{

publicintremoveElement(int[]nums,intval){

intslow=0;

for(intfast=0;fast<nums.length;fast++){

//保留不等于val的有效元素

if(nums[fast]!=val){

nums[slow]=nums[fast];

slow++;

}

}

returnslow;

}

}答案解析：时间复杂度O(n)，空间复杂度O(1)，完全满足原地修改的要求。面试常问变种：有序数组去重，核心逻辑和双指针思路一致，是数组类问题的核心解题模板。二、链表经典面试题1.反转单链表（LeetCode206）题目描述：给你单链表的头节点head，请你反转链表，并返回反转后的链表头节点。解题思路：迭代解法（面试优先写迭代，递归可作为拓展）。定义前驱节点、当前节点，遍历链表，逐个反转节点指向。每次保存当前节点的后继节点，将当前节点指向前驱节点，再平移前驱、当前节点，直至遍历结束。java

classListNode{

intval;

ListNodenext;

ListNode(){}

ListNode(intval){this.val=val;}

ListNode(intval,ListNodenext){this.val=val;this.next=next;}

}

publicclassReverseList{

publicListNodereverseList(ListNodehead){

ListNodepre=null;

ListNodecur=head;

while(cur!=null){

//保存下一个节点

ListNodenext=cur.next;

//反转当前节点指向

cur.next=pre;

//指针后移

pre=cur;

cur=next;

}

//pre为新链表头节点

returnpre;

}

}答案解析：迭代解法时间O(n)，空间O(1)，是面试最优解。递归解法空间复杂度为O(n)，存在栈溢出风险，工程中不推荐。面试官常追问：链表反转的迭代和递归区别、手写完整测试流程。2.链表中环的检测（LeetCode141）题目描述：给你一个链表的头节点head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表存在环。解题思路：快慢指针（龟兔赛跑）。快指针每次走两步，慢指针每次走一步。如果链表有环，快慢指针一定会相遇；如果快指针走到null，说明无环。java

publicclassHasCycle{

publicbooleanhasCycle(ListNodehead){

ListNodeslow=head;

ListNodefast=head;

while(fast!=null&&fast.next!=null){

slow=slow.next;

fast=fast.next.next;

//指针相遇，存在环

if(slow==fast){

returntrue;

}

}

returnfalse;

}

}答案解析：时间O(n)，空间O(1)，优于哈希集合存储节点的解法。进阶面试题：找到环的入口节点，核心是在相遇后，重置指针同步遍历，首次相遇点即为环入口。三、字符串高频算法1.有效的括号（LeetCode20）题目描述：给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合、左括号必须以正确的顺序闭合、每个右括号都有一个对应的相同类型的左括号。解题思路：栈的经典应用。遍历字符串，遇到左括号，将对应的右括号入栈；遇到右括号，判断栈顶元素是否和当前元素一致。最终栈为空则括号全部匹配有效。java

importjava.util.Deque;

importjava.util.LinkedList;

publicclassValidBracket{

publicbooleanisValid(Strings){

Deque<Character>stack=newLinkedList<>();

for(charc:s.toCharArray()){

if(c=='('){

stack.push(')');

}elseif(c=='{'){

stack.push('}');

}elseif(c=='['){

stack.push(']');

}elseif(stack.isEmpty()||stack.pop()!=c){

//无匹配左括号或括号类型不匹配

returnfalse;

}

}

//栈空代表全部匹配完成

returnstack.isEmpty();

}

}答案解析：利用栈先进后出的特性，完美适配括号嵌套匹配场景。时间O(n)，空间O(n)。面试重点考察栈的使用场景，以及边界条件判断（空字符串、单个括号、嵌套错乱括号）。四、排序与查找算法1.二分查找（LeetCode704）题目描述：给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。解题思路：有序数组专属二分查找。定义左右边界，循环取中间值，对比中间值和目标值，收缩左右边界。注意边界条件避免死循环。java

publicclassBinarySearch{

publicintsearch(int[]nums,inttarget){

intleft=0;

intright=nums.length-1;

//闭区间[left,right]

while(left<=right){

//防止溢出，等价于(left+right)/2

intmid=left+(right-left)/2;

if(nums[mid]==target){

returnmid;

}elseif(nums[mid]<target){

//目标在右区间

left=mid+1;

}else{

//目标在左区间

right=mid-1;

}

}

return-1;

}

}答案解析：时间复杂度O(logn)，是有序数组最优查找算法。面试高频追问：为什么用left+(right-left)/2？避免left+right超出int最大值导致溢出。同时需要区分开闭区间的写法区别。2.快速排序（手写实现）题目描述：手写Java快速排序算法，实现数组从小到大排序。解题思路：分治思想。选取基准值，将数组分区，左区间元素小于基准值，右区间大于基准值，递归排序左右子区间。java

publicclassQuickSort{

publicvoidquickSort(int[]nums,intleft,intright){

if(left>=right){

return;

}

//分区操作，返回基准值下标

intpivotIndex=partition(nums,left,right);

//递归排序左区间

quickSort(nums,left,pivotIndex-1);

//递归排序右区间

quickSort(nums,pivotIndex+1,right);

}

privateintpartition(int[]nums,intleft,intright){

//选取最左侧为基准值

intpivot=nums[left];

intl=left;

intr=right;

while(l<r){

//从右往左找小于基准的值

while(l<r&&nums[r]>=pivot){

r--;

}

//从左往右找大于基准的值

while(l<r&&nums[l]<=pivot){

l++;

}

//交换左右指针元素

inttemp=nums[l];

nums[l]=nums[r];

nums[r]=temp;

}

//基准值归位

nums[left]=nums[l];

nums[l]=pivot;

returnl;

}

}答案解析：平均时间复杂度O(nlogn)，最坏O(n²)，空间复杂度O(logn)。面试必问：快排不稳定、优化方案（三数取中、随机基准、小数组插排）、快排和归并排序的区别。五、动态规划基础（中级面试）1.爬楼梯（LeetCode70）题目描述：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶？解题思路：动态规划。第n阶楼梯的方法数=第n-1阶（爬1步）+第n-2阶（爬2步），推导公式dp[n]=dp[n-1]+dp[n-2]。采用变量迭代压缩空间，无需数组。java

publicclassClimbStairs{

publicintclimbStairs(intn){

if(n<=2){

returnn;

}

inta=1;

intb=2;

intres=0;

for(inti=3;i<=n;i++){

res=a+b;

a=b;

b=res;

}

returnres;

}

}答案解析：时间O(n)，空间O(1)。本质是斐波那契数列变形，面试主要考察动态规划的状态推导能力，是DP入门核心题。进阶可考最小花费爬楼梯、不同路径等同类题目。六、二叉树基础面试题1.二叉树前序遍历（递归+迭代）题目描述：给你二叉树的根节点root，返回它节点值的前序遍历（根-左-右）。java

importjava.util.ArrayList;

importjava.util.Deque;

importjava.util.LinkedList;

importjava.util.List;

classTreeNode{

intval;

TreeNodeleft;

TreeNoderight;

TreeNode(){}

TreeNode(intval){this.val=val;}

TreeNode(intval,TreeNodeleft,TreeNoderight){

this.val=val;

this.left=left;

this.right=right;

}

}

//递归解法

publicclassPreOrderTraversal{

List<Integer>res=newArrayList<>();

publicList<Integer>preorderTraversal(TreeNoderoot){

if(root==null){

returnres;

}

res.add(root.val);

preorderTraversal(root.left);

preorderTraversal(root.right);

returnres;

}

//迭代栈解法（面试推荐）

publicList<Integer>preorderIter(TreeNoderoot){

List<Integer>res=newArrayList<>();