> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/jian-guo/two-sum.md).

# Two Sum

<https://leetcode.com/problems/two-sum/description/>

> Given an array of integers, return indices of the two numbers such that they add up to a specific target.
>
> You may assume that each input would have exactly one solution, and you may not use the same element twice.

## Thoughts

思路实际和背包很像，看是否能选几个元素凑够特定的数。只是它规定了只选了两个物品，因此比背包简单，不需要双重循环。

## Code

```
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.keySet().contains(target - nums[i])) {
                res[0] = map.get(target - nums[i]);
                res[1] = i;
                return res;
            }
            map.put(nums[i], i);
        }

        return res;
    }
}
```

## Analysis

Errors:

1. 由于不是排好序的，因此不能直接使用2 sum。

时间复杂O(n), 空间复杂度O(n).