Java 面试算法题全解析：案例、讲解与面试频率分析

2026-01-05 02:27

在 Java 面试中，算法题几乎是必考内容。掌握常见算法题不仅能加深编程能力，还能提高面试通过率。本篇文章将结合经典案例，详细讲解题解思路、实现代码，以及面试中出现的频率，帮助你有针对性地准备。

1. 两数之和（Two Sum）

面试频率：⭐⭐⭐⭐⭐（非常高）
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在数组中找出 两个数，使它们的和等于目标值，并返回它们的下标。

示例：

java

复制代码

输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]
解释: nums[0] + nums[1] = 2 + 7 = 9

解题思路：

暴力法：双重循环检查每一对元素，时间复杂度 O(n²)。
哈希表法：用一个 Map 存储数字及其索引，遍历数组时检查 target - num 是否存在，时间复杂度 O(n)，空间复杂度 O(n)。

Java 实现：

java

复制代码

import java.util.*;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solution");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum(nums, target)));
    }
}

面试要点：

注意考虑重复数字和数组长度为零的情况。
能说出暴力法与哈希表法的复杂度对比。

2. 链表反转（Reverse Linked List）

面试频率：⭐⭐⭐⭐（高）
题目描述：
反转一个单链表。

示例：

java

复制代码

输入: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
输出: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

解题思路：

迭代法：使用三个指针 prev, curr, next。
递归法：递归到链表尾部，再逐步反转指针。

Java 实现（迭代）：

java

复制代码

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseLinkedList {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

面试要点：

能熟练写出迭代和递归版本。
理解指针的移动过程，防止丢链表节点。

3. 二分查找（Binary Search）

面试频率：⭐⭐⭐⭐⭐（非常高）
题目描述：
在一个 有序数组 中查找指定元素的下标，如果不存在返回 -1。

示例：

java

复制代码

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4

解题思路：

利用数组有序性，每次比较中间元素。
如果中间值大于目标，搜索左半边；否则搜索右半边。
时间复杂度 O(log n)。

Java 实现：

java

复制代码

public class BinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

面试要点：

注意 mid 计算防止溢出：mid = left + (right-left)/2。
能写出递归版本更佳。

4. 合并两个有序数组（Merge Two Sorted Arrays）

面试频率：⭐⭐⭐（中等）
题目描述：
给定两个有序数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 仍然有序。

示例：

java

复制代码

输入: nums1 = [1,2,3,0,0,0], m = 3
      nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

解题思路：

从后往前合并，避免覆盖 nums1 的数据。
时间复杂度 O(m+n)。

Java 实现：

java

复制代码

public class MergeSortedArray {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

面试要点：

能说明从后向前合并的原因。
注意边界条件，nums2 为空或 nums1 空位足够时的情况。

5. 拓展：面试常见算法类型

类型	题目示例	面试频率
数组与字符串	两数之和、三数之和、最长回文子串	高
链表	反转链表、合并链表、环检测	高
栈与队列	最小栈、括号匹配	中
哈希表	两数之和、字母异位词	高
排序与搜索	二分查找、快速排序、合并排序	高
动态规划	爬楼梯、背包问题、最长公共子序列	高
图算法	BFS、DFS、最短路径、拓扑排序	中