数组与哈希简单3 种解法

#1两数之和

在数组中找到和为 target 的两个不同元素下标；题目保证恰有一个答案。

#数组#哈希表#双指针

解题主线

哈希表保存已经扫描过的值到下标，当前只查 target - nums[i]，天然避免重复使用同一元素。

排序双指针若要返回原下标，必须让值与原下标绑定；直接排序 nums 后返回排序下标是错误的。

解法 1：双重枚举

枚举所有 i < j 的下标对，首次命中目标和即返回。

时间复杂度

O(n²)

空间复杂度

O(1)

1. 两数之和 · 双重枚举

java

final class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((long) nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[0];
    }
}

枚举所有 i < j 的下标对，首次命中目标和即返回。

解法 2：一次遍历哈希表

扫描当前值前查询补数是否已出现；命中时返回补数下标与当前下标。

时间复杂度

O(n) 期望

空间复杂度

O(n)

1. 两数之和 · 一次遍历哈希表

java

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)

1. 两数之和 · 携带原下标排序 + 双指针

java

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