题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，且数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

Constraints:

• 2 <= nums.length <= $10^4$
• -$10^9$ <= nums[i] <= $10^9$
• -$10^9$ <= target <= $10^9$
• Only one valid answer exists.

提示：

• 2 <= nums.length <= $10^4$
• -$10^9$ <= nums[i] <= $10^9$
• -$10^9$ <= target <= $10^9$
• 只会存在一个有效答案

Follow-up:

Can you come up with an algorithm that is less than O($n^2$) time complexity?

进阶：

你可以想出一个时间复杂度小于 O($n^2$) 的算法吗？

解题思路

方法一：暴力

我们通过遍历数组每个元素x，寻找tatget-x，且数组每个元素只能出现一次所以只要寻找x后面的元素。

Python代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

class Solution {
    public int[] twoSum(int[] nums, int target) {
        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];
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[