1. 两数之和
查看题目简单
数组
哈希表
频率: 5
解法一：暴力解法
时间复杂度：O(n²) | 空间复杂度：O(1) | 推荐使用
动画演示
准备就绪 - 点击开始按钮查看动画
代码实现
class Solution {
/**
* 暴力解法
* 枚举所有可能的两数组合，时间复杂度O(n²)
*/
public int[] twoSum(int[] nums, int target) {
if (nums == null) {
return null;
}
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
result[0] = i;
for (int j = i + 1; j < nums.length; j++) {
result[1] = j;
if (nums[result[0]] + nums[result[1]] == target) {
return result;
}
}
}
return result;
}
}时间复杂度：O(n²)
空间复杂度：O(1)
算法思路：
暴力解法通过双重循环枚举所有可能的两数组合，直到找到和为target的组合。
核心思想：
1. 外层循环：遍历数组每个元素，索引i从0到n-1
2. 内层循环：对于每个i，遍历i之后的元素，索引j从i+1到n-1
3. 检查nums[i] + nums[j]是否等于target
4. 如果相等，返回[i, j]；否则继续查找
复杂度分析：
- 时间复杂度：O(n²)，需要两层循环，最坏情况下需要比较n(n-1)/2次
- 空间复杂度：O(1)，只使用了常数额外空间，不随输入规模变化
解法二：哈希表优化
时间复杂度：O(n) | 空间复杂度：O(n)
动画演示
准备就绪 - 点击开始按钮查看动画
代码实现
class Solution {
/**
* 哈希表优化解法
* 使用HashMap存储已遍历的元素，实现O(n)时间复杂度
*/
public int[] twoSum(int[] nums, int target) {
// hashtable的key为数组的值，value为数组的下标
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}时间复杂度：O(n)
空间复杂度：O(n)
算法思路：
使用哈希表优化两数之和问题，将时间复杂度从O(n²)降低到O(n)。
核心思想：
1. 遍历数组，对于每个元素nums[i]，计算需要的配对值：target - nums[i]
2. 查询哈希表中是否存在该配对值
3. 如果存在，直接返回两个索引
4. 如果不存在，将当前元素值和索引存入哈希表，继续遍历
复杂度分析：
- 时间复杂度：O(n)，只需遍历数组一次，哈希表提供O(1)的查找时间
- 空间复杂度：O(n)，最坏情况下需要存储n-1个元素到哈希表