算法能力是Java后端开发者的核心硬实力，无论是校招入门、社招晋升，还是业务代码的性能优化，扎实的算法功底都是拉开差距的关键。
前置环境与依赖
本文所有代码基于JDK 17编写，核心maven依赖如下：
<dependencies>
<!-- lombok -->
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<version>1.18.32</version>
<scope>provided</scope>
</dependency>
<!-- spring核心工具类 -->
<dependency>
<groupId>org.springframework</groupId>
<artifactId>spring-core</artifactId>
<version>6.1.6</version>
</dependency>
<!-- guava集合工具类 -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>33.1.0-jre</version>
</dependency>
<!-- fastjson2 -->
<dependency>
<groupId>com.alibaba.fastjson2</groupId>
<artifactId>fastjson2</artifactId>
<version>2.0.49</version>
</dependency>
<!-- slf4j-api -->
<dependency>
<groupId>org.slf4j</groupId>
<artifactId>slf4j-api</artifactId>
<version>2.0.13</version>
</dependency>
</dependencies>
一、只出现一次的数字
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 示例1： 输入：nums = [2,2,1] 输出：1 示例2： 输入：nums = [4,1,2,1,2] 输出：4
核心原理拆解
本题的核心考点是位运算特性、哈希表统计与数学逻辑推导，其中位运算方案是时间与空间复杂度最优的解法。核心基础知识点：
- 异或运算的核心特性：
- 任何数和自身异或，结果为0：
a ^ a = 0 - 任何数和0异或，结果为自身：
a ^ 0 = a - 异或运算满足交换律和结合律：
a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b
- 哈希表统计：通过键值对记录每个数字的出现次数，最终筛选出次数为1的数字，是最直观的通用解法。
- 数学公式推导：利用
2*(所有不重复数字的和) - 原数组的和 = 只出现一次的数字，适用于其余数字均出现两次的限定场景。
实现方案
方案1：异或运算（最优解）
方案原理
利用异或运算的交换律与结合律，将数组中所有元素依次异或，最终剩余的结果就是只出现一次的数字。该方案无需额外的存储空间，是本题的最优解。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import java.util.Arrays;
/**
* 只出现一次的数字
* @author ken
*/
@Slf4j
public class SingleNumberSolution {
/**
* 异或运算解法
* @param nums 输入的整数数组
* @return 只出现一次的数字
*/
public static int singleNumberXOR(int[] nums) {
if (ObjectUtils.isEmpty(nums)) {
throw new IllegalArgumentException("数组不能为空");
}
return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
}
public static void main(String[] args) {
int[] nums1 = {2, 2, 1};
int[] nums2 = {4, 1, 2, 1, 2};
log.info("示例1结果:{}", singleNumberXOR(nums1));
log.info("示例2结果:{}", singleNumberXOR(nums2));
}
}
复杂度分析
- 时间复杂度：O(n)，仅需遍历数组一次
- 空间复杂度：O(1)，仅使用常数级额外空间
方案2：哈希表统计次数
方案原理
通过Java Stream的分组统计功能，统计每个数字的出现次数，最终过滤出出现次数为1的数字。该方案逻辑直观，可扩展至其余数字出现任意次数的场景。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
/**
* 只出现一次的数字
* @author ken
*/
@Slf4j
public class SingleNumberSolution {
/**
* 哈希表统计解法
* @param nums 输入的整数数组
* @return 只出现一次的数字
*/
public static int singleNumberHashMap(int[] nums) {
if (ObjectUtils.isEmpty(nums)) {
throw new IllegalArgumentException("数组不能为空");
}
Map<Integer, Long> countMap = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
return countMap.entrySet().stream()
.filter(entry -> entry.getValue() == 1)
.map(Map.Entry::getKey)
.findFirst()
.orElseThrow(() -> new IllegalArgumentException("数组中无符合条件的数字"));
}
public static void main(String[] args) {
int[] nums1 = {2, 2, 1};
int[] nums2 = {4, 1, 2, 1, 2};
log.info("示例1结果:{}", singleNumberHashMap(nums1));
log.info("示例2结果:{}", singleNumberHashMap(nums2));
}
}
复杂度分析
- 时间复杂度：O(n)，需遍历数组统计次数，再遍历哈希表筛选结果
- 空间复杂度：O(n)，需额外的哈希表存储数字出现次数
方案3：数学公式推导
方案原理
基于题目限定条件（其余元素均出现两次），通过数学公式计算得到结果。核心逻辑为：所有重复元素在2*去重和中被计算两次，减去原数组和后，剩余的就是只出现一次的数字。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import java.util.Arrays;
/**
* 只出现一次的数字
* @author ken
*/
@Slf4j
public class SingleNumberSolution {
/**
* 数学公式解法
* @param nums 输入的整数数组
* @return 只出现一次的数字
*/
public static int singleNumberMath(int[] nums) {
if (ObjectUtils.isEmpty(nums)) {
throw new IllegalArgumentException("数组不能为空");
}
int sumDistinct = Arrays.stream(nums).distinct().sum();
int sumTotal = Arrays.stream(nums).sum();
return 2 * sumDistinct - sumTotal;
}
public static void main(String[] args) {
int[] nums1 = {2, 2, 1};
int[] nums2 = {4, 1, 2, 1, 2};
log.info("示例1结果:{}", singleNumberMath(nums1));
log.info("示例2结果:{}", singleNumberMath(nums2));
}
}
复杂度分析
- 时间复杂度：O(n)，需遍历数组计算去重和与总和
- 空间复杂度：O(n)，需额外空间存储去重后的元素
方案横向对比
| 实现方案 | 时间复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
| 异或运算 | O(n) | O(1) | 时空复杂度最优，代码极简 | 本题限定场景，其余元素均出现两次 |
| 哈希表统计 | O(n) | O(n) | 逻辑通用，可扩展至任意出现次数 | 不限定其余元素的出现次数，通用场景 |
| 数学公式 | O(n) | O(n) | 思路巧妙，逻辑直观 | 严格限定其余元素均出现两次的场景 |
二、搜索旋转排序数组
题目描述
整数数组nums按升序排列，数组中的值互不相同。在传递给函数之前，nums在预先未知的某个下标k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。 示例1： 输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4 示例2： 输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1 示例3： 输入：nums = [1], target = 0 输出：-1
核心原理拆解
本题的核心考点是二分查找算法的灵活应用，旋转后的数组虽然整体无序，但可划分为两个升序的子数组，且其中一个子数组一定是完全有序的。核心逻辑是通过二分查找判断mid左右哪一段是有序的，再判断target是否落在有序区间内，逐步缩小查找范围，将时间复杂度从线性查找的O(n)优化至O(log n)。
二分查找核心边界规则：
- mid计算采用
left + (right - left) / 2，避免(left + right)直接相加导致的整数溢出 - 循环条件为
left <= right，确保区间内最后一个元素被检查 - 区间收缩时，
left = mid + 1、right = mid - 1，避免死循环
实现方案
方案1：经典二分查找（最优解）
方案原理
直接利用旋转数组的部分有序特性，通过一次二分查找完成目标值的定位。每次二分后，判断左半段或右半段是否有序，再根据target与有序区间边界的大小关系，收缩查找区间。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
/**
* 搜索旋转排序数组
* @author ken
*/
@Slf4j
public class SearchRotatedArraySolution {
/**
* 经典二分查找解法
* @param nums 旋转后的升序数组
* @param target 目标查找值
* @return 目标值的下标，不存在返回-1
*/
public static int searchBinary(int[] nums, int target) {
if (ObjectUtils.isEmpty(nums)) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
log.info("示例1结果:{}", searchBinary(nums, 0));
log.info("示例2结果:{}", searchBinary(nums, 3));
log.info("示例3结果:{}", searchBinary(new int[]{1}, 0));
}
}
复杂度分析
- 时间复杂度：O(log n)，二分查找每次将查找区间缩小一半
- 空间复杂度：O(1)，仅使用常数级额外空间
方案2：旋转点定位+两次二分查找
方案原理
先通过二分查找找到数组的旋转点（即数组中最小元素的下标），将旋转数组拆分为两个独立的升序子数组，再分别对两个子数组执行标准二分查找，最终返回目标值的下标。该方案逻辑拆分清晰，更易于理解。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
/**
* 搜索旋转排序数组
* @author ken
*/
@Slf4j
public class SearchRotatedArraySolution {
/**
* 旋转点定位+两次二分查找解法
* @param nums 旋转后的升序数组
* @param target 目标查找值
* @return 目标值的下标，不存在返回-1
*/
public static int searchRotatePoint(int[] nums, int target) {
if (ObjectUtils.isEmpty(nums)) {
return -1;
}
int n = nums.length;
int left = 0;
int right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
int rotateIndex = left;
int leftResult = binarySearch(nums, 0, rotateIndex - 1, target);
if (leftResult != -1) {
return leftResult;
}
return binarySearch(nums, rotateIndex, n - 1, target);
}
/**
* 标准升序数组二分查找
* @param nums 升序数组
* @param left 查找区间左边界
* @param right 查找区间右边界
* @param target 目标查找值
* @return 目标值下标，不存在返回-1
*/
private static int binarySearch(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
log.info("示例1结果:{}", searchRotatePoint(nums, 0));
log.info("示例2结果:{}", searchRotatePoint(nums, 3));
log.info("示例3结果:{}", searchRotatePoint(new int[]{1}, 0));
}
}
复杂度分析
- 时间复杂度：O(log n)，查找旋转点为O(log n)，两次二分查找均为O(log n)，整体仍为对数级别
- 空间复杂度：O(1)，仅使用常数级额外空间
方案3：Stream API线性查找
方案原理
通过Java Stream的IntStream生成数组下标，过滤出数组值等于target的下标，直接返回结果。该方案代码极简，适用于小数据量场景。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import java.util.stream.IntStream;
/**
* 搜索旋转排序数组
* @author ken
*/
@Slf4j
public class SearchRotatedArraySolution {
/**
* Stream API线性查找解法
* @param nums 旋转后的升序数组
* @param target 目标查找值
* @return 目标值的下标，不存在返回-1
*/
public static int searchStream(int[] nums, int target) {
if (ObjectUtils.isEmpty(nums)) {
return -1;
}
return IntStream.range(0, nums.length)
.filter(i -> nums[i] == target)
.findFirst()
.orElse(-1);
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
log.info("示例1结果:{}", searchStream(nums, 0));
log.info("示例2结果:{}", searchStream(nums, 3));
log.info("示例3结果:{}", searchStream(new int[]{1}, 0));
}
}
复杂度分析
- 时间复杂度：O(n)，需遍历整个数组
- 空间复杂度：O(1)，仅使用常数级额外空间
方案横向对比
| 实现方案 | 时间复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
| 经典二分查找 | O(log n) | O(1) | 时空效率最优，一次遍历完成 | 大数据量、高性能要求的生产场景 |
| 旋转点+两次二分 | O(log n) | O(1) | 逻辑拆分清晰，易于理解和调试 | 学习入门、需要分步调试的场景 |
| Stream线性查找 | O(n) | O(1) | 代码极简，可读性强 | 小数据量、快速实现的场景 |
三、合并区间
题目描述
以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 示例1： 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6] 示例2： 输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间
核心原理拆解
本题的核心考点是贪心算法与区间排序，核心逻辑是：
- 区间重叠的前提：按区间左边界排序后，若后一个区间的左边界小于等于前一个区间的右边界，则两个区间重叠，可合并为一个新的区间，新区间的右边界为两个区间右边界的最大值。
- 贪心策略：按左边界排序后，每次合并都尽可能扩大当前区间的右边界，确保覆盖所有重叠的区间。
实现方案
方案1：排序+列表遍历合并（最优解）
方案原理
先按区间的左边界进行升序排序，再遍历排序后的区间，维护一个结果列表，每次将当前区间与结果列表中最后一个区间对比，若重叠则合并，否则直接加入结果列表。该方案是工业界最常用的实现，逻辑清晰，效率最优。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* 合并区间
* @author ken
*/
@Slf4j
public class MergeIntervalsSolution {
/**
* 排序+列表遍历合并解法
* @param intervals 输入的区间数组
* @return 合并后的不重叠区间数组
*/
public static int[][] mergeClassic(int[][] intervals) {
if (ObjectUtils.isEmpty(intervals) || intervals.length == 1) {
return intervals;
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
List<int[]> result = new ArrayList<>();
result.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] lastInterval = result.get(result.size() - 1);
int[] currentInterval = intervals[i];
if (currentInterval[0] <= lastInterval[1]) {
lastInterval[1] = Math.max(lastInterval[1], currentInterval[1]);
} else {
result.add(currentInterval);
}
}
return result.toArray(new int[result.size()][]);
}
public static void main(String[] args) {
int[][] intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
int[][] intervals2 = {{1, 4}, {4, 5}};
log.info("示例1结果:{}", Arrays.deepToString(mergeClassic(intervals1)));
log.info("示例2结果:{}", Arrays.deepToString(mergeClassic(intervals2)));
}
}
复杂度分析
- 时间复杂度：O(n log n)，排序的时间复杂度为O(n log n)，遍历区间为O(n)，整体由排序操作主导
- 空间复杂度：O(log n)，排序所需的栈空间，结果存储的空间不计入额外空间复杂度
方案2：Stream API+Reduce累积合并
方案原理
通过Java Stream的sorted方法完成区间排序，再通过reduce方法实现区间的累积合并逻辑，将合并逻辑封装为函数式表达式，符合Java8+的函数式编程风格。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* 合并区间
* @author ken
*/
@Slf4j
public class MergeIntervalsSolution {
/**
* Stream+Reduce累积合并解法
* @param intervals 输入的区间数组
* @return 合并后的不重叠区间数组
*/
public static int[][] mergeStreamReduce(int[][] intervals) {
if (ObjectUtils.isEmpty(intervals) || intervals.length == 1) {
return intervals;
}
List<int[]> result = Arrays.stream(intervals)
.sorted(Comparator.comparingInt(a -> a[0]))
.reduce(
new ArrayList<>(),
(list, interval) -> {
if (list.isEmpty()) {
list.add(interval);
} else {
int[] last = list.get(list.size() - 1);
if (interval[0] <= last[1]) {
last[1] = Math.max(last[1], interval[1]);
} else {
list.add(interval);
}
}
return list;
},
(list1, list2) -> list1
);
return result.toArray(new int[result.size()][]);
}
public static void main(String[] args) {
int[][] intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
int[][] intervals2 = {{1, 4}, {4, 5}};
log.info("示例1结果:{}", Arrays.deepToString(mergeStreamReduce(intervals1)));
log.info("示例2结果:{}", Arrays.deepToString(mergeStreamReduce(intervals2)));
}
}
复杂度分析
- 时间复杂度：O(n log n)，与经典解法一致，排序操作主导时间复杂度
- 空间复杂度：O(log n)，排序所需的栈空间
方案3：排序+双端队列Deque实现
方案原理
使用Deque双端队列存储合并后的区间，利用Deque的peekLast()方法快速获取队列尾部的最后一个区间，合并时先移除尾部区间，再添加合并后的新区间，逻辑更贴合队列的操作特性，避免对列表元素的直接修改。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
/**
* 合并区间
* @author ken
*/
@Slf4j
public class MergeIntervalsSolution {
/**
* 排序+Deque双端队列解法
* @param intervals 输入的区间数组
* @return 合并后的不重叠区间数组
*/
public static int[][] mergeDeque(int[][] intervals) {
if (ObjectUtils.isEmpty(intervals) || intervals.length == 1) {
return intervals;
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
Deque<int[]> deque = new LinkedList<>();
deque.addLast(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = deque.peekLast();
int[] current = intervals[i];
if (current[0] <= last[1]) {
deque.removeLast();
deque.addLast(new int[]{last[0], Math.max(last[1], current[1])});
} else {
deque.addLast(current);
}
}
return deque.toArray(new int[deque.size()][]);
}
public static void main(String[] args) {
int[][] intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
int[][] intervals2 = {{1, 4}, {4, 5}};
log.info("示例1结果:{}", Arrays.deepToString(mergeDeque(intervals1)));
log.info("示例2结果:{}", Arrays.deepToString(mergeDeque(intervals2)));
}
}
复杂度分析
- 时间复杂度：O(n log n)，与经典解法一致
- 空间复杂度：O(log n)，排序所需的栈空间
方案横向对比
| 实现方案 | 时间复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
| 排序+列表遍历 | O(n log n) | O(log n) | 逻辑直观，效率最优，工业界标准实现 | 生产环境、高性能要求场景 |
| Stream+Reduce | O(n log n) | O(log n) | 函数式编程风格，代码简洁优雅 | 响应式编程、函数式开发场景 |
| 排序+Deque | O(n log n) | O(log n) | 操作符合队列特性，无列表元素原地修改 | 对数据不可变性有要求的场景 |
四、大数相加（两个字符串相加）
题目描述
给定两个字符串形式的非负整数num1和num2，返回它们的和，同样以字符串形式返回。你不能使用任何内建的用于处理大整数的库，也不能直接将输入的字符串转换为整数形式。 示例1： 输入：num1 = "21543655", num2 = "4332656442" 输出："4354200097" 示例2： 输入：num1 = "0", num2 = "0" 输出："0"
核心原理拆解
本题的核心考点是模拟十进制加法的底层逻辑，解决Java中基础数据类型无法存储超长整数的问题。核心逻辑是：
- 从两个字符串的末尾（即数字的最低位）开始，逐位相加，同时记录进位。
- 若其中一个字符串已遍历完毕，则补0参与计算，直到两个字符串都遍历完毕且无进位剩余。
- 由于计算结果是从低位到高位存储的，最终需要反转得到正序的结果字符串。
实现方案
方案1：双指针逐位相加（最优解）
方案原理
用两个指针分别指向两个字符串的末尾，逐位取出数字相加，计算当前位的结果和进位，将当前位结果存入StringBuilder，最终反转StringBuilder得到最终结果。该方案是工业界最常用的实现，时空效率最优。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
/**
* 大数相加
* @author ken
*/
@Slf4j
public class BigNumberAddSolution {
/**
* 双指针逐位相加解法
* @param num1 第一个数字字符串
* @param num2 第二个数字字符串
* @return 两个数字的和，字符串形式
*/
public static String addStringsClassic(String num1, String num2) {
if (!StringUtils.hasText(num1)) {
return num2;
}
if (!StringUtils.hasText(num2)) {
return num1;
}
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
StringBuilder result = new StringBuilder();
while (i >= 0 || j >= 0 || carry > 0) {
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = n1 + n2 + carry;
result.append(sum % 10);
carry = sum / 10;
i--;
j--;
}
return result.reverse().toString();
}
public static void main(String[] args) {
log.info("示例1结果:{}", addStringsClassic("21543655", "4332656442"));
log.info("示例2结果:{}", addStringsClassic("0", "0"));
}
}
复杂度分析
- 时间复杂度：O(max(n,m))，n和m分别为两个字符串的长度，需遍历较长的字符串一次
- 空间复杂度：O(max(n,m))，存储结果所需的StringBuilder空间
方案2：Stream API+AtomicInteger函数式实现
方案原理
通过Java Stream生成索引，从后往前逐位处理两个字符串的数字，使用AtomicInteger维护进位值（解决Stream中无法修改外部变量的问题），最终通过Stream反转结果得到正序的和。该方案符合Java8+的函数式编程风格。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
/**
* 大数相加
* @author ken
*/
@Slf4j
public class BigNumberAddSolution {
/**
* Stream+AtomicInteger函数式解法
* @param num1 第一个数字字符串
* @param num2 第二个数字字符串
* @return 两个数字的和，字符串形式
*/
public static String addStringsStream(String num1, String num2) {
if (!StringUtils.hasText(num1)) {
return num2;
}
if (!StringUtils.hasText(num2)) {
return num1;
}
int maxLen = Math.max(num1.length(), num2.length());
AtomicInteger carry = new AtomicInteger(0);
List<String> digits = IntStream.range(0, maxLen)
.mapToObj(i -> {
char c1 = i < num1.length() ? num1.charAt(num1.length() - 1 - i) : '0';
char c2 = i < num2.length() ? num2.charAt(num2.length() - 1 - i) : '0';
int n1 = c1 - '0';
int n2 = c2 - '0';
int sum = n1 + n2 + carry.get();
carry.set(sum / 10);
return String.valueOf(sum % 10);
})
.collect(Collectors.toList());
if (carry.get() > 0) {
digits.add(String.valueOf(carry.get()));
}
return IntStream.range(0, digits.size())
.mapToObj(i -> digits.get(digits.size() - 1 - i))
.collect(Collectors.joining());
}
public static void main(String[] args) {
log.info("示例1结果:{}", addStringsStream("21543655", "4332656442"));
log.info("示例2结果:{}", addStringsStream("0", "0"));
}
}
复杂度分析
- 时间复杂度：O(max(n,m))，与经典解法一致
- 空间复杂度：O(max(n,m))，存储中间结果和最终结果所需的空间
方案3：Deque双端队列实现
方案原理
使用Deque双端队列存储每一位的计算结果，通过addFirst()方法将当前位结果从队列头部插入，最终直接拼接队列元素即可得到正序的结果，无需额外的反转操作。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
import java.util.Deque;
import java.util.LinkedList;
/**
* 大数相加
* @author ken
*/
@Slf4j
public class BigNumberAddSolution {
/**
* Deque双端队列解法
* @param num1 第一个数字字符串
* @param num2 第二个数字字符串
* @return 两个数字的和，字符串形式
*/
public static String addStringsDeque(String num1, String num2) {
if (!StringUtils.hasText(num1)) {
return num2;
}
if (!StringUtils.hasText(num2)) {
return num1;
}
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
Deque<String> deque = new LinkedList<>();
while (i >= 0 || j >= 0 || carry > 0) {
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = n1 + n2 + carry;
deque.addFirst(String.valueOf(sum % 10));
carry = sum / 10;
i--;
j--;
}
return String.join("", deque);
}
public static void main(String[] args) {
log.info("示例1结果:{}", addStringsDeque("21543655", "4332656442"));
log.info("示例2结果:{}", addStringsDeque("0", "0"));
}
}
复杂度分析
- 时间复杂度：O(max(n,m))，与经典解法一致
- 空间复杂度：O(max(n,m))，队列存储结果所需的空间
方案横向对比
| 实现方案 | 时间复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
| 双指针逐位相加 | O(max(n,m)) | O(max(n,m)) | 时空效率最优，逻辑直观，工业界标准实现 | 生产环境、超长数字处理场景 |
| Stream函数式实现 | O(max(n,m)) | O(max(n,m)) | 函数式编程风格，无显式循环 | 响应式编程、函数式开发场景 |
| Deque双端队列 | O(max(n,m)) | O(max(n,m)) | 无需反转操作，直接生成正序结果 | 对字符串反转操作有性能顾虑的场景 |
五、有效括号匹配
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。 示例1： 输入：s = "()" 输出：true 示例2： 输入：s = "()[]{}" 输出：true 示例3： 输入：s = "(]" 输出：false
核心原理拆解
本题的核心考点是栈数据结构的应用，括号匹配的核心逻辑是后进先出：最后出现的左括号，必须最先被闭合。核心规则：
- 遇到左括号，将其压入栈中。
- 遇到右括号，检查栈是否为空，若为空则直接无效；若不为空，弹出栈顶的左括号，检查是否与当前右括号类型匹配，不匹配则直接无效。
- 遍历完成后，若栈为空，则所有括号都匹配成功，否则无效。
实现方案
方案1：Deque栈+哈希映射（最优解）
方案原理
使用Deque作为栈的实现（Java官方推荐使用Deque替代Stack类），通过哈希映射存储右括号到对应左括号的映射，遍历字符串时，左括号入栈，右括号则通过映射表快速匹配栈顶元素，最终判断栈是否为空。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/**
* 有效括号匹配
* @author ken
*/
@Slf4j
public class ValidParenthesesSolution {
private static final Map<Character, Character> BRACKET_MAP = Stream.of(new Object[][]{
{')', '('},
{']', '['},
{'}', '{'}
}).collect(Collectors.toMap(
data -> (Character) data[0],
data -> (Character) data[1]
));
/**
* Deque栈+哈希映射解法
* @param s 输入的括号字符串
* @return 括号是否有效
*/
public static boolean isValidClassic(String s) {
if (!StringUtils.hasText(s)) {
return true;
}
if (s.length() % 2 != 0) {
return false;
}
Deque<Character> stack = new LinkedList<>();
for (char c : s.toCharArray()) {
if (!BRACKET_MAP.containsKey(c)) {
stack.push(c);
} else {
if (stack.isEmpty() || stack.pop() != BRACKET_MAP.get(c)) {
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
log.info("示例1结果:{}", isValidClassic("()"));
log.info("示例2结果:{}", isValidClassic("()[]{}"));
log.info("示例3结果:{}", isValidClassic("(]"));
}
}
复杂度分析
- 时间复杂度：O(n)，仅需遍历字符串一次
- 空间复杂度：O(n)，最坏情况下（全为左括号），栈需要存储所有字符
方案2：数组模拟栈（性能最优）
方案原理
使用数组模拟栈结构，通过栈顶指针维护栈的状态，避免Deque包装类的性能开销，直接通过字符的ASCII码进行匹配判断，是性能最优的实现方案。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
/**
* 有效括号匹配
* @author ken
*/
@Slf4j
public class ValidParenthesesSolution {
/**
* 数组模拟栈解法
* @param s 输入的括号字符串
* @return 括号是否有效
*/
public static boolean isValidArray(String s) {
if (!StringUtils.hasText(s)) {
return true;
}
int length = s.length();
if (length % 2 != 0) {
return false;
}
char[] stack = new char[length];
int top = -1;
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack[++top] = c;
} else {
if (top == -1) {
return false;
}
char topChar = stack[top--];
if ((c == ')' && topChar != '(')
|| (c == ']' && topChar != '[')
|| (c == '}' && topChar != '{')) {
return false;
}
}
}
return top == -1;
}
public static void main(String[] args) {
log.info("示例1结果:{}", isValidArray("()"));
log.info("示例2结果:{}", isValidArray("()[]{}"));
log.info("示例3结果:{}", isValidArray("(]"));
}
}
复杂度分析
- 时间复杂度：O(n)，仅需遍历字符串一次
- 空间复杂度：O(n)，数组存储所需的空间，无额外包装类开销
方案3：Stream API+Reduce函数式实现
方案原理
通过Java Stream将字符串转换为字符流，使用reduce方法累积维护栈的状态与匹配结果，通过自定义状态类封装栈和有效标志，全程采用函数式编程风格，无显式循环。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
import java.util.Deque;
import java.util.LinkedList;
/**
* 有效括号匹配
* @author ken
*/
@Slf4j
public class ValidParenthesesSolution {
/**
* 括号匹配状态封装类
*/
static class BracketState {
Deque<Character> stack;
boolean valid;
public BracketState(Deque<Character> stack, boolean valid) {
this.stack = stack;
this.valid = valid;
}
}
/**
* Stream+Reduce函数式解法
* @param s 输入的括号字符串
* @return 括号是否有效
*/
public static boolean isValidStream(String s) {
if (!StringUtils.hasText(s)) {
return true;
}
if (s.length() % 2 != 0) {
return false;
}
BracketState finalState = s.chars()
.mapToObj(c -> (char) c)
.reduce(
new BracketState(new LinkedList<>(), true),
(state, c) -> {
if (!state.valid) {
return state;
}
Deque<Character> stack = state.stack;
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
return new BracketState(stack, true);
} else {
if (stack.isEmpty()) {
return new BracketState(stack, false);
}
char top = stack.pop();
boolean match = (c == ')' && top == '(')
|| (c == ']' && top == '[')
|| (c == '}' && top == '{');
return new BracketState(stack, match);
}
},
(state1, state2) -> state1
);
return finalState.valid && finalState.stack.isEmpty();
}
public static void main(String[] args) {
log.info("示例1结果:{}", isValidStream("()"));
log.info("示例2结果:{}", isValidStream("()[]{}"));
log.info("示例3结果:{}", isValidStream("(]"));
}
}
复杂度分析
- 时间复杂度：O(n)，仅需遍历字符串一次
- 空间复杂度：O(n)，栈存储所需的空间
方案横向对比
| 实现方案 | 时间复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
| Deque栈+哈希映射 | O(n) | O(n) | 逻辑直观，易于扩展，Java官方推荐实现 | 生产环境、通用业务场景 |
| 数组模拟栈 | O(n) | O(n) | 性能最优，无包装类开销 | 高性能要求、高频调用场景 |
| Stream函数式实现 | O(n) | O(n) | 函数式编程风格，无显式循环 | 响应式编程、函数式开发场景 |
六、电话号码的字母组合
题目描述
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。数字到字母的映射与电话按键相同，1不对应任何字母。 电话按键映射： 2:abc，3:def，4:ghi，5:jkl，6:mno，7:pqrs，8:tuv，9:wxyz 示例1： 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例2： 输入：digits = "" 输出：[] 示例3： 输入：digits = "2" 输出：["a","b","c"]
核心原理拆解
本题的核心考点是回溯算法（深度优先搜索DFS）与广度优先搜索BFS，本质是求解多组集合的笛卡尔积。核心逻辑：
- 回溯算法：通过递归逐位处理数字，遍历当前数字对应的所有字母，拼接成临时组合后递归处理下一位数字，递归终止时将完整组合加入结果集，再回溯删除当前字母，尝试其他可能。
- 广度优先搜索：通过队列逐层构建组合，每处理一个数字，将队列中已有的所有组合与当前数字的所有字母拼接，生成新的组合存入队列，最终队列中的元素即为所有完整组合。
实现方案
方案1：回溯算法（DFS，最优解）
方案原理
通过回溯算法递归构建所有可能的字母组合，使用StringBuilder维护当前拼接的组合，递归终止时将组合加入结果集，再通过删除最后一个字符完成回溯，尝试其他字母。该方案是本题的经典实现，时空效率最优。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
import java.util.ArrayList;
import java.util.List;
/**
* 电话号码的字母组合
* @author ken
*/
@Slf4j
public class LetterCombinationsSolution {
private static final String[] DIGIT_MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
/**
* 回溯算法解法
* @param digits 输入的数字字符串
* @return 所有可能的字母组合
*/
public List<String> letterCombinationsBacktrack(String digits) {
List<String> result = new ArrayList<>();
if (!StringUtils.hasText(digits)) {
return result;
}
backtrack(digits, 0, new StringBuilder(), result);
return result;
}
/**
* 回溯递归函数
* @param digits 输入的数字字符串
* @param index 当前处理的数字索引
* @param current 当前拼接的字母组合
* @param result 结果集
*/
private void backtrack(String digits, int index, StringBuilder current, List<String> result) {
if (index == digits.length()) {
result.add(current.toString());
return;
}
int digit = digits.charAt(index) - '0';
String letters = DIGIT_MAP[digit];
for (char c : letters.toCharArray()) {
current.append(c);
backtrack(digits, index + 1, current, result);
current.deleteCharAt(current.length() - 1);
}
}
public static void main(String[] args) {
LetterCombinationsSolution solution = new LetterCombinationsSolution();
log.info("示例1结果:{}", solution.letterCombinationsBacktrack("23"));
log.info("示例2结果:{}", solution.letterCombinationsBacktrack(""));
log.info("示例3结果:{}", solution.letterCombinationsBacktrack("2"));
}
}
复杂度分析
- 时间复杂度：O(3^m * 4^n)，m为对应3个字母的数字个数，n为对应4个字母的数字个数，需遍历所有可能的组合
- 空间复杂度：O(m+n)，递归调用栈的深度为数字字符串的长度
方案2：BFS队列+Stream实现
方案原理
使用Deque队列实现广度优先搜索，初始队列存入空字符串，每处理一个数字，通过Java Stream将队列中的所有组合与当前数字的字母拼接，生成新的队列，最终队列中的元素即为所有完整的字母组合。该方案无递归，避免了递归栈溢出的风险。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
/**
* 电话号码的字母组合
* @author ken
*/
@Slf4j
public class LetterCombinationsSolution {
private static final String[] DIGIT_MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
/**
* BFS队列+Stream解法
* @param digits 输入的数字字符串
* @return 所有可能的字母组合
*/
public List<String> letterCombinationsBFS(String digits) {
if (!StringUtils.hasText(digits)) {
return new ArrayList<>();
}
Deque<String> deque = new LinkedList<>();
deque.add("");
for (char c : digits.toCharArray()) {
int digit = c - '0';
String letters = DIGIT_MAP[digit];
deque = deque.stream()
.flatMap(s -> letters.chars().mapToObj(ch -> s + (char) ch))
.collect(Collectors.toCollection(LinkedList::new));
}
return new ArrayList<>(deque);
}
public static void main(String[] args) {
LetterCombinationsSolution solution = new LetterCombinationsSolution();
log.info("示例1结果:{}", solution.letterCombinationsBFS("23"));
log.info("示例2结果:{}", solution.letterCombinationsBFS(""));
log.info("示例3结果:{}", solution.letterCombinationsBFS("2"));
}
}
复杂度分析
- 时间复杂度：O(3^m * 4^n)，需遍历所有可能的组合
- 空间复杂度：O(3^m * 4^n)，队列需要存储所有可能的组合
方案3：Stream API+Reduce函数式实现
方案原理
通过Java Stream的reduce方法，以包含空字符串的列表为初始值，逐位处理数字，将当前列表中的所有组合与当前数字的字母拼接，生成新的列表，最终得到所有可能的字母组合。该方案全程采用函数式编程风格，代码极简。
package com.jam.demo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
/**
* 电话号码的字母组合
* @author ken
*/
@Slf4j
public class LetterCombinationsSolution {
private static final String[] DIGIT_MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
/**
* Stream+Reduce函数式解法
* @param digits 输入的数字字符串
* @return 所有可能的字母组合
*/
public List<String> letterCombinationsStreamReduce(String digits) {
if (!StringUtils.hasText(digits)) {
return Collections.emptyList();
}
return digits.chars()
.mapToObj(c -> c - '0')
.reduce(
Collections.singletonList(""),
(list, digit) -> list.stream()
.flatMap(s -> DIGIT_MAP[digit].chars().mapToObj(c -> s + (char) c))
.collect(Collectors.toList()),
(list1, list2) -> list1
);
}
public static void main(String[] args) {
LetterCombinationsSolution solution = new LetterCombinationsSolution();
log.info("示例1结果:{}", solution.letterCombinationsStreamReduce("23"));
log.info("示例2结果:{}", solution.letterCombinationsStreamReduce(""));
log.info("示例3结果:{}", solution.letterCombinationsStreamReduce("2"));
}
}
复杂度分析
- 时间复杂度：O(3^m * 4^n)，需遍历所有可能的组合
- 空间复杂度：O(3^m * 4^n)，需存储所有可能的组合
方案横向对比
| 实现方案 | 时间复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
| 回溯算法DFS | O(3^m * 4^n) | O(m+n) | 空间效率最优，逻辑清晰，经典实现 | 通用场景、面试首选方案 |
| BFS队列+Stream | O(3^m * 4^n) | O(3^m * 4^n) | 无递归，避免栈溢出风险，逻辑直观 | 超长数字字符串、避免递归的场景 |
| Stream+Reduce | O(3^m * 4^n) | O(3^m * 4^n) | 函数式编程风格，代码极简优雅 | 响应式编程、函数式开发场景 |
写在最后
本文覆盖的6道算法题，是Java后端开发面试中最高频的考点，不仅考察算法逻辑，更考验开发者对Java语言特性的掌握程度与代码规范的理解。每一道题的多种实现方案，都对应了不同的业务场景与开发风格，大家可根据实际需求选择合适的实现。算法能力的提升，从来不是靠死记硬背，而是理解底层逻辑，多写多练，将算法思维融入到日常的业务代码开发中，才能真正做到融会贯通。
