数组与哈希简单3 种解法
#1两数之和
在数组中找到和为 target 的两个不同元素下标；题目保证恰有一个答案。
#数组#哈希表#双指针
原题
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
解题主线
- 哈希表保存已经扫描过的值到下标，当前只查 target - nums[i]，天然避免重复使用同一元素。
- 排序双指针若要返回原下标，必须让值与原下标绑定；直接排序 nums 后返回排序下标是错误的。
解法 1：双重枚举
枚举所有 i < j 的下标对，首次命中目标和即返回。
-
时间复杂度： O(n²)
-
空间复杂度： O(1)
final class Solution {
public int[] twoSum(int[] nums, int target) {
// 只枚举 i < j，保证两个下标不同且每个下标对仅检查一次。
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
// 先提升为 long，避免两个 int 相加时溢出后误判。
if ((long) nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
return new int[0];
}
}解法 2：一次遍历哈希表
扫描当前值前查询补数是否已出现；命中时返回补数下标与当前下标。
-
时间复杂度： O(n) 期望
-
空间复杂度： O(n)
import java.util.HashMap;
import java.util.Map;
final class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> indexByValue = new HashMap<>();
// 循环开始时，哈希表只包含当前下标之前的元素。
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
// 先查询再写入，避免把同一个元素同时当作两个加数。
Integer previous = indexByValue.get(complement);
if (previous != null) {
return new int[] {previous, i};
}
indexByValue.put(nums[i], i);
}
return new int[0];
}
}解法 3：携带原下标排序 + 双指针
把每个值与原下标封装后按值排序，两端根据和向中间收缩。
-
时间复杂度： O(n log n)
-
空间复杂度： O(n)
import java.util.Arrays;
import java.util.Comparator;
final class Solution {
private record Entry(int value, int index) {}
public int[] twoSum(int[] nums, int target) {
// 排序前绑定原下标，避免排序后丢失题目要求的返回位置。
Entry[] entries = new Entry[nums.length];
for (int i = 0; i < nums.length; i++) {
entries[i] = new Entry(nums[i], i);
}
Arrays.sort(entries, Comparator.comparingInt(Entry::value));
int left = 0;
int right = entries.length - 1;
// 有序区间中，当前两端之外的错误方向可整段排除。
while (left < right) {
long sum = (long) entries[left].value() + entries[right].value();
if (sum == target) {
return new int[] {entries[left].index(), entries[right].index()};
}
// 和偏小只能增大左端，和偏大只能减小右端。
if (sum < target) left++;
else right--;
}
return new int[0];
}
}实现提示
- 修复旧代码直接排序 nums、因而返回错误原下标的问题。
边界与易错点
- 必须先查补数再写入当前值，否则 target = 2 * nums[i] 时可能重复使用同一下标。
- 无解分支不应静默返回 [0, 0]；这里返回空数组，使非法状态不伪装成答案。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q001_twoSum.java