← 返回首页 ❓ 面试题库
📑 本篇章节导航 (共9章,点击直达)
一、复杂度分析二、数组与字符串三、链表四、树五、排序算法六、经典题型七、Java集合源码八、面试高频综合题面试速记口诀

Q136 数据结构与算法面试实战

20K Java+AI 岗位高频考点 — 算法是大厂面试的必考环节,后端面试常考数组、链表、树、排序、二分、动态规划。覆盖高频LeetCode题型、Java集合源码分析、时间空间复杂度、解题套路。

一、复杂度分析

1. 时间空间复杂度?


大O表示法:描述算法运行时间/空间随输入规模的增长趋势

常见复杂度(从小到大):
O(1)     哈希查找
O(logN)  二分查找
O(N)     线性遍历
O(NlogN) 排序(快排/归并)
O(N²)    冒泡/选择排序
O(2^N)   暴力子集
O(N!)    全排列

分析技巧:
- 看循环层数:单层O(N),双层O(N²)
- 看递归深度:树高logN → O(logN)
- 看分支数:每层分2支 → O(2^N)

空间复杂度:
- 原地操作:O(1)
- 辅助数组:O(N)
- 递归栈:O(深度)
- Map/Set:O(N)

二、数组与字符串

2. 两数之和?


// LeetCode #1 两数之和
// 给定数组和target,找两个数之和等于target的索引
// 时间O(N) 空间O(N)
public 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);
    }
    return new int[0];
}
// 核心:HashMap一遍扫描,空间换时间

3. 三数之和?


// LeetCode #15 三数之和
// 时间O(N²) 空间O(1)(不计返回结果)
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(List.of(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}
// 核心:排序+双指针,固定一个数,剩下两个用双指针

4. 最长无重复子串?


// LeetCode #3 无重复字符的最长子串
// 滑动窗口 时间O(N) 空间O(字符集)
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int maxLen = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (window.containsKey(c)) {
            left = Math.max(left, window.get(c) + 1);
        }
        window.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// 核心:滑动窗口+HashMap记录字符最新位置

三、链表

5. 反转链表?


// LeetCode #206 反转链表
// 迭代 时间O(N) 空间O(1)
public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 递归 时间O(N) 空间O(N)
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

6. 链表常见题型?


// 1. 检测环(快慢指针)
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

// 2. 合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
        else { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = l1 != null ? l1 : l2;
    return dummy.next;
}

// 3. 找中间节点(快慢指针)
public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

四、树

7. 二叉树遍历?


// 前序(根→左→右)
public List<Integer> preorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

// 中序(左→根→右):BST得到有序序列
public List<Integer> inorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

// 层序(BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

8. 二叉搜索树(BST)?


BST性质:左子树 < 根 < 右子树

中序遍历BST = 有序序列

常见操作时间复杂度:O(H)(H=树高)
- 平衡BST:H = logN
- 退化BST:H = N(退化为链表)

Java中:
TreeMap = 红黑树(自平衡BST)
TreeSet = 红黑树

红黑树性质:
1. 节点是红色或黑色
2. 根是黑色
3. 叶子(nil)是黑色
4. 红色节点的子节点是黑色
5. 从任一节点到叶子的路径含相同数量黑色节点

HashMap JDK8+:链表长度≥8 → 树化为红黑树
红黑树长度≤6 → 退化为链表

五、排序算法

9. 排序算法对比?


| 算法 | 平均 | 最差 | 空间 | 稳定 |
|------|------|------|------|------|
| 冒泡 | O(N²) | O(N²) | O(1) | 是 |
| 选择 | O(N²) | O(N²) | O(1) | 否 |
| 插入 | O(N²) | O(N²) | O(1) | 是 |
| 快排 | O(NlogN) | O(N²) | O(logN) | 否 |
| 归并 | O(NlogN) | O(NlogN) | O(N) | 是 |
| 堆排 | O(NlogN) | O(NlogN) | O(1) | 否 |
| 计数 | O(N+K) | O(N+K) | O(K) | 是 |
| 基数 | O(N×K) | O(N×K) | O(N+K) | 是 |

面试重点:
1. 快排:平均最快,实际应用最广
2. 归并:稳定排序,适合链表和外部排序
3. 堆排:原地排序,适合Top-K问题

Java中:
Arrays.sort() → 基本类型用双轴快排,对象用TimSort(归并+插入)
Collections.sort() → TimSort

10. 快速排序?


public void quickSort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = partition(nums, lo, hi);
    quickSort(nums, lo, pivot - 1);
    quickSort(nums, pivot + 1, hi);
}

private int partition(int[] nums, int lo, int hi) {
    int pivot = nums[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (nums[j] < pivot) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, hi);
    return i;
}

// 优化:随机选择pivot避免最坏情况
// Java Arrays.sort用双轴快排(Dual-Pivot Quicksort)

六、经典题型

11. 二分查找?


// 标准二分(找目标值)
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// 找左边界(第一个>=target)
public int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 应用:旋转数组查找、搜索插入位置、求平方根

12. 动态规划(DP)?


DP解题四步:
1. 定义状态:dp[i]代表什么
2. 状态转移:dp[i] = f(dp[i-1], ...)
3. 初始条件:dp[0] = ?
4. 计算顺序:从小到大

经典题目:
1. 爬楼梯:dp[i] = dp[i-1] + dp[i-2]
2. 最长递增子序列:dp[i] = max(dp[j]+1) for j<i, nums[j]<nums[i]
3. 0-1背包:dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi)
4. 最长公共子序列:dp[i][j] = dp[i-1][j-1]+1 if s1[i]==s2[j]
5. 编辑距离:dp[i][j] = min(插入,删除,替换)

// LeetCode #70 爬楼梯
public int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// LeetCode #300 最长递增子序列
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int maxLen = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

13. Top-K问题?


// 方法一:小顶堆(适合大数据量/流式数据)
public int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) heap.poll(); // 弹出最小的
    }
    return heap.stream().mapToInt(i -> i).toArray();
}

// 方法二:快速选择(平均O(N))
public int findKthLargest(int[] nums, int k) {
    k = nums.length - k; // 第K大 = 第(N-K)小
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int pivot = partition(nums, lo, hi);
        if (pivot < k) lo = pivot + 1;
        else if (pivot > k) hi = pivot - 1;
        else break;
    }
    return nums[k];
}

七、Java集合源码

14. HashMap源码分析?


JDK 1.8 HashMap:
数组 + 链表 + 红黑树

put流程:
1. hash(key) → 扰动函数(h ^ h>>>16)减少碰撞
2. (n-1) & hash → 定位桶(n为2的幂次方)
3. 桶为空 → 直接放入
4. 桶不为空:
   a. key相等 → 覆盖
   b. 红黑树 → 树插入
   c. 链表 → 尾插(JDK7头插会死循环)
      链表长度≥8且数组≥64 → 树化
5. 检查扩容:size > threshold → resize()

扩容(resize):
- 新数组 = 旧数组 × 2
- 元素重新hash分布(高位0留在原位,高位1移到新位置)
- 默认初始容量16,负载因子0.75
- threshold = capacity × loadFactor

为什么容量是2的幂?
(n-1) & hash 等价于 hash % n(位运算更快)

15. ArrayList vs LinkedList?


| 维度 | ArrayList | LinkedList |
|------|-----------|-----------|
| 底层 | 动态数组 | 双向链表 |
| 随机访问 | O(1) | O(N) |
| 头部插入 | O(N) | O(1) |
| 尾部插入 | 均摊O(1) | O(1) |
| 内存 | 连续 | 分散(指针开销) |
| 缓存 | 友好 | 不友好 |

ArrayList扩容:
- 默认容量10
- 扩容1.5倍(newCapacity = old + old>>1)
- Arrays.copyOf复制

面试结论:99%场景用ArrayList

八、面试高频综合题

16. 刷题策略?


LeetCode Hot 100 + 面试高频200

题型优先级(后端面试):
1. 数组/字符串:双指针、滑动窗口
2. 链表:反转、合并、环
3. 树:遍历、BST、DFS/BFS
4. 二分查找:标准模板、变体
5. 排序:快排、归并
6. 动态规划:背包、子序列
7. 图:DFS、BFS、拓扑排序
8. 堆:Top-K、中位数

刷题节奏:
- 每个类型先做3-5道基础题
- 总结模板/套路
- 再做变体和hard
- 面试前集中复习Hot100

面试技巧:
- 先说思路(不急着写代码)
- 说清时间空间复杂度
- 考虑边界条件(null/空/1个元素)
- 先暴力解法再优化

面试速记口诀

数组三技巧:双指针(两端逼近)、滑动窗口(子串子数组)、前缀和(区间求和)

>

链表三套路:快慢指针(环/中点)、dummy节点(头插)、递归(反转)

>

树三遍历:前中后(DFS递归/栈)、层序(BFS队列)

>

DP四步:定义状态→转移方程→初始条件→计算顺序