大厂算法面试 7 天冲刺：第 1 天 - 深度剖析数组与字符串高频算法（Java 实战）

第1天：数组与字符串算法实战（Java 实现）

1. 典型问题分析

问题1：两数之和（Two Sum）

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在数组中找出 和为目标值 的那 两个整数，并返回它们的数组下标。

示例

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

2. 解决方案（多种方式）

方法1：暴力枚举（O(n²))

思路：

使用两层 for 循环遍历数组的所有可能的数对，检查它们的和是否等于 target。

public int[] twoSumBruteForce(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[]{}; // 没有找到返回空数组
}

缺点：时间复杂度 O(n²)，适用于小规模数据。

方法2：哈希表优化（O(n)）

思路：

使用 HashMap 存储遍历过的数字和它们的索引。
遍历数组时，计算 target - nums[i] 是否已在 HashMap 中，如果存在，则直接返回两个索引。

import java.util.HashMap;
import java.util.Map;public int[] twoSumHashMap(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[]{};
}

优点：

通过 HashMap 进行 O(1) 查询，时间复杂度 O(n)，适用于大规模数据。
空间复杂度为 O(n)，因为 HashMap 需要额外存储元素。

问题2：最长无重复子串（Longest Substring Without Repeating Characters）

题目描述

给定一个字符串 s，请你找出其中 不含重复字符的最长子串 的长度。

示例

输入: s = "abcabcbb"
输出: 3
解释: 最长不重复子串是 "abc"，长度为3。

2. 解决方案（多种方式）

方法1：暴力枚举（O(n²))

思路：

逐个遍历子串，检查是否有重复字符，更新最长长度。

public int lengthOfLongestSubstringBruteForce(String s) {int maxLength = 0;for (int i = 0; i < s.length(); i++) {for (int j = i; j < s.length(); j++) {if (hasDuplicate(s, i, j)) break;maxLength = Math.max(maxLength, j - i + 1);}}return maxLength;
}private boolean hasDuplicate(String s, int start, int end) {Set<Character> set = new HashSet<>();for (int i = start; i <= end; i++) {if (set.contains(s.charAt(i))) return true;set.add(s.charAt(i));}return false;
}

缺点：时间复杂度 O(n²)，适用于小规模字符串。

方法2：滑动窗口（O(n)）

思路：

使用 双指针（left, right） 和 HashSet 记录窗口内字符。
移动右指针 扩展窗口，如果出现重复字符，则 移动左指针 缩小窗口，直到没有重复字符。

import java.util.HashSet;
import java.util.Set;public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>();int maxLength = 0, left = 0;for (int right = 0; right < s.length(); right++) {while (set.contains(s.charAt(right))) {set.remove(s.charAt(left));left++;}set.add(s.charAt(right));maxLength = Math.max(maxLength, right - left + 1);}return maxLength;
}

优点：

时间复杂度 O(n)，比暴力解法更高效。
适用于 大规模字符串处理。

问题3：最大子数组和（Kadane’s Algorithm）

题目描述

给定一个整数数组 nums，找到 连续子数组（最少包含一个元素），使其和最大，并返回最大和。

示例

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

2. 解决方案

方法1：暴力枚举（O(n²))

思路：

计算所有可能的子数组和，找出最大值。

public int maxSubArrayBruteForce(int[] nums) {int maxSum = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++) {int sum = 0;for (int j = i; j < nums.length; j++) {sum += nums[j];maxSum = Math.max(maxSum, sum);}}return maxSum;
}

缺点：时间复杂度 O(n²)，适用于小规模数据。

方法2：Kadane’s Algorithm（O(n)）

思路：

动态规划思想：dp[i] 代表 以 nums[i] 结尾的最大子数组和。
递推公式：
- dp[i] = max(dp[i-1] + nums[i], nums[i])
- 只需维护 currentSum 变量，优化为 O(1) 空间。

public int maxSubArray(int[] nums) {int maxSum = nums[0], currentSum = nums[0];for (int i = 1; i < nums.length; i++) {currentSum = Math.max(currentSum + nums[i], nums[i]);maxSum = Math.max(maxSum, currentSum);}return maxSum;
}