---
title: LeetCode:1. 两数之和
abbrlink: 2f3d653d
date: "2024-09-15 20:31:15"
updated: "2024-09-15 20:31:17"
desc: 在这个方法中，HashMap扮演了非常重要的角色。它允许我们在O(1)时间复杂度内检查一个数是否已经在之前遍历过的元素中出现过，并且还能够获取到这个数在数组中的索引。这种方法比暴力解法（即使用两层循环遍历数组）要高效得多，因为暴力解法的时间复杂度是O(n^2)，而这种方法的时间复杂度是O(n)。
categories:
    - 算法题
tags:
    - leetcode
    - 算法题
    - java
    - 学习
    - 进步
cover: https://leetcode.cn/favicon.ico
---

_我不想O(n^2) :(_

<!--more-->

## 前置声明

> ## <div style="text-align: center;"> LeetCode所有题目版权均归 LeetCode 和 力扣中国 所有</div><div style="text-align: center;"> 本文仅提题解与思路，详情请访问官网查看 </div>
>
> ---
>
> <center>
>
> [![LeetCode Logo](https://leetcode.cn/favicon.ico)][2]
>
> </center>
> <center>
>
> [LeetCode:1. 两数之和][2]
>
> </center>
>
> [2]: https://leetcode.cn/problems/two-sum/description/

## O(n)解法:hashmap

下面是我直接用AI写的：
在这个方法中，HashMap扮演了非常重要的角色。它允许我们在O(1)时间复杂度内检查一个数是否已经在之前遍历过的元素中出现过，并且还能够获取到这个数在数组中的索引。这种方法比暴力解法（即使用两层循环遍历数组）要高效得多，因为暴力解法的时间复杂度是O(n^2)，而这种方法的时间复杂度是O(n)。

需要注意的是，HashMap中的键（key）是数组中的元素值，而值（value）是这些元素值在数组中的索引。这种方法利用了HashMap能够快速查找键的特性，从而避免了不必要的重复遍历。

最后，如果遍历完整个数组都没有找到满足条件的两个数，那么方法会抛出一个IllegalArgumentException异常。

```java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(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);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

```

## O(nlog(n))解法：

我第一眼想到先用对儿值记录值和索引
通过对值进行排序，再用双指针扫两端
这样匹配后可以获得排序之前的索引

> 不太会java，还是得靠AI找包和各种方法：（

```java

import java.util.Arrays;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个可排序的数组来保存值和索引
        int[][] indexedNums = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            indexedNums[i] = new int[]{nums[i], i};
        }

        // 按照值对数组进行排序
        Arrays.sort(indexedNums, (a, b) -> Integer.compare(a[0], b[0]));

        // 初始化两个指针
        int left = 0, right = nums.length - 1;

        // 使用双指针技术寻找匹配对
        while (left < right) {
            int currentSum = indexedNums[left][0] + indexedNums[right][0];
            if (currentSum == target) {
                // 返回原始索引
                return new int[]{indexedNums[left][1], indexedNums[right][1]};
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }

        // 如果没有找到匹配项，则返回空数组
        return new int[]{};
    }
}
```


---

**作者：**xingwangzhe

**本文链接：**[https://xingwangzhe.fun/posts/2f3d653d/](https://xingwangzhe.fun/posts/2f3d653d/)

本文采用[知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议](https://creativecommons.org/licenses/by-nc-sa/4.0/)进行许可。