Java 算法面试高频题（含详细答案解析）

Java算法面试高频题（含详细答案解析）本文收录互联网大厂Java后端面试最常考的5道算法题，涵盖数组、链表、哈希、双指针、动态规划核心考点，每题包含题干、解题思路、完整可运行代码、细节解析，适配校招、社招面试场景。一、两数之和（简单·必考题）1.题目描述给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例：输入：nums=[2,7,11,15],target=9输出：[0,1]解释：因为nums[0]+nums[1]==9，返回[0,1]。2.解题思路1.暴力解法：双层循环遍历数组，两两求和比对，时间复杂度O(n²)，效率较低，面试不推荐；2.哈希表解法：利用HashMap存储数组值和对应下标，遍历数组时，计算差值target-当前值，判断差值是否已存在于Map中；3.若存在，直接返回当前下标和Map中存储的差值下标；若不存在，将当前数值和下标存入Map，单次遍历即可完成，时间复杂度O(n)。3.完整代码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，供后续元素匹配

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

}

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

returnnewint[0];

}

}4.详细解析核心优化点：用空间换时间，将查找时间从O(n)降为O(1)。遍历过程中先查后存，完美避免同一个元素重复使用的问题。面试加分点：面试官常问「为什么不先存后查」，先存后查会导致当前元素自身匹配（如target=4，数组[2,2]），逻辑出错，先校验再存入是最优写法。二、反转单链表（简单·链表必考）1.题目描述给你单链表的头节点head，请你反转链表，并返回反转后的链表头节点。示例：输入：head=[1,2,3,4,5]输出：[5,4,3,2,1]2.解题思路采用迭代双指针法，核心是逐个反转节点指向：1.定义前驱节点pre（初始为null）、当前节点cur（初始为头节点）；2.循环遍历链表，每次先保存当前节点的下一个节点（防止断链）；3.将当前节点的next指向前驱节点，完成单次反转；4.前驱节点、当前节点依次后移，直到当前节点为null，此时pre即为新链表头节点。3.完整代码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;

}

}4.详细解析时间复杂度O(n)，仅遍历一次链表；空间复杂度O(1)，仅使用常数额外空间，是面试最优解。常见踩坑点：未提前保存next节点，导致链表断链，无法继续遍历。递归解法可作为拓展，但递归深度过大会栈溢出，工程中优先迭代法。三、有效的括号（简单·栈经典题）1.题目描述给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合；每个右括号都有一个对应的相同类型的左括号。示例：输入s="()[]{}"，输出true；输入s="(]"，输出false。2.解题思路利用栈「后进先出」的特性匹配括号：1.遍历字符串每个字符，遇到左括号，将对应的右括号入栈；2.遇到右括号，判断栈是否为空，或栈顶元素是否和当前字符相等；3.不匹配直接返回false，匹配则弹出栈顶元素；4.遍历结束后，栈为空说明所有括号完全匹配，否则匹配失败。3.完整代码java

importjava.util.Stack;

publicclassValidBracket{

publicbooleanisValid(Strings){

Stack<Character>stack=newStack<>();

for(charc:s.toCharArray()){

//左括号入栈对应右括号

if(c=='('){

stack.push(')');

}elseif(c=='{'){

stack.push('}');

}elseif(c=='['){

stack.push(']');

}else{

//右括号：栈空或栈顶不匹配，直接失败

if(stack.isEmpty()||stack.pop()!=c){

returnfalse;

}

}

}

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

returnstack.isEmpty();

}

}4.详细解析该写法简化了传统map匹配方式，代码更简洁、执行效率更高。核心逻辑：左括号存预期的右括号，遍历到右括号时直接比对，顺序完全契合栈的特性。边界场景覆盖：空字符串、单括号、顺序错乱括号、嵌套括号，全部兼容。四、最长无重复子串（中等·双指针高频）1.题目描述给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。示例：输入s="abcabcbb"，输出3，解释：无重复最长子串为"abc"，长度为3。2.解题思路滑动窗口（双指针）+哈希表解法：1.用HashMap存储字符及最后出现的下标，left为窗口左边界，right为窗口右边界；2.遍历字符串，若当前字符已存在且下标在窗口内，更新左边界为重复字符下一位；3.每次更新字符最新下标，并计算当前窗口长度，记录最大值；4.遍历结束后返回最大长度。3.完整代码java

importjava.util.HashMap;

importjava.util.Map;

publicclassLongestSubstring{

publicintlengthOfLongestSubstring(Strings){

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

intmaxLen=0;

intleft=0;

for(intright=0;right<s.length();right++){

charc=s.charAt(right);

//字符重复且在当前窗口内，移动左指针

if(map.containsKey(c)&&map.get(c)>=left){

left=map.get(c)+1;

}

//更新字符最新下标

map.put(c,right);

//更新最大长度

maxLen=Math.max(maxLen,right-left+1);

}

returnmaxLen;

}

}4.详细解析时间复杂度O(n)，仅一次遍历字符串；空间复杂度O(1)，字符为有限ASCII字符，哈希表大小恒定。核心细节：必须判断重复字符下标是否在窗口内，避免窗口左边界回退。例如字符串"abba"，防止错误更新left指针。是面试重点考察的细节点。五、爬楼梯（简单·动态规划入门必考）1.题目描述假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶？示例：输入n=3，输出3。解释：1+1+1、1+2、2+1，共3种方法。2.解题思路动态规划核心递推逻辑：1.状态定义：dp[i]代表爬到第i阶楼梯的方法数；2.递推公式：最后一步只能走1阶或2阶，所以dp[i]=dp[i-1]+dp[i-2]；3.初始状态：dp[1]=1，dp[2]=2；4.优化空间：无需数组，仅用两个变量迭代更新，空间复杂度降为O(1)。3.完整代码java

publicclassClimbStairs{

publicintclimbStairs(intn){

//边界条件

if(n<=2){

returnn;

}

intpre1=1;

intpre2=2;

intcur=0;

//从第3阶开始迭代计算

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

cur=pre1+pre2;

pre1=pre2;

pre2=cur;

}

retu