【Day 19 】2021-12-30 - 两数之和

[azl397985856]

两数之和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/two-sum

前置知识

• 哈希表

  题目描述

  
  给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
  示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[Joyce94]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i=0; i<nums.length; i++){
            if (map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]), i};  // 不能少了new
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

[lilililisa1998]

暴力解法

    # for i in range(len(nums)):
    #     for j in range(i+1,len(nums)):
    #         if nums[i]+nums[j]==target:
    #             return [i,j]

    #哈希表
    hashmap={}
    for i in range(len(nums)):
        if target-nums[i] in hashmap:
            return [hashmap[target-nums[i]],i]
        else:
            hashmap[nums[i]]=i

[GaoMinghao]

思路

利用HashMap存储已遍历的值

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> records = new HashMap<>();
        int[] result = new int[2];
        for(int i = 0; i < nums.length;i++) {
            if(records.get(target-nums[i])!=null) {
                result[0] = i;
                result[1] = records.get(target-nums[i]);
            }else {
                records.put(nums[i],i);
            }
        }
        return result;
    }
}

时间复杂度

O(n)

[iambigchen]

思路

遍历，并用hashmap存下每个值，计算当前值-目标值，看hashmap中是否存在。

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = {}
    for (let index = 0; index < nums.length; index++) {
        const e = nums[index];
        let sur = target - e
        if (map[sur] !== undefined) {
            return [map[sur], index]
        }
        map[e] = index
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[caohaha]

思路

利用hash表空间换时间，遍历数组，查看target-nums[i]是否存在

C++实现

class Solution 
{
    public:
        vector<int> twoSum(vector<int>& nums, int target) 
        {
            unordered_map<int,int> my_map;
            vector<int> result;
            for(int i=0; i<nums.size();i++)
            {
                my_map[nums[i]]=i;
            }
            for(int i=0;i<nums.size();i++)
            {
                auto iter = my_map.find(target-nums[i]);
                if(iter != my_map.end() && iter->second>i)
                {
                    result.push_back(i);
                    result.push_back(iter->second);
                }
            }
            return result;
        }

};

复杂度分析

• 时间复杂度O(n)
• 空间复杂度O(n)

[suukii]

Link to LeetCode Problem

S1: 哈希表

暴力法两层循环时间是 $O(N^2)$。

双指针的话要求数组先排序，时间 $O(NlogN)$，还要 $O(N)$ 的辅助空间来记录原下标。

本题较好的解决方法是借助哈希表，在遍历数组的同时把数字和下标存进哈希表中，并检查 目标值 - 当前数字 是否存在于哈希表中，有的话直接返回结果，没有就继续遍历。

由于不能使用同一个元素，要注意先检查，再将当前数字加入哈希表。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> seen;
        for (int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            auto search = seen.find(diff);
            if (search != seen.end())
                return vector<int>{search->second, i};
            seen[nums[i]] = i;
        }
        // NOTREACHED
        return vector<int>{-1, -1};
    }
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    if (!nums || !nums.length) return [];

    const map = {};
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const diff = target - num;

        if (diff in map) return [map[diff], i];
        map[num] = i;
    }
};

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        for i, n in enumerate(nums):
            diff = target - n
            if diff in hashmap:
                return [hashmap[diff], i]
            hashmap[n] = i

• Time: $O(N)$，N 为数组长度，最坏的情况下数组中的每个元素都被访问一次，访问数组元素的时间是 $O(1)$，哈希表插入和查询元素的时间也是 $O(1)$。
• Space: $O(N)$，N 为数组长度，用来存元素和下标的哈希表所需的空间。

[ZJP1483469269]

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

[tangjy149]

思路

暴力求解：两层循环，不进行列举 加入hash表，对出现过的数字进行存储，使得查找便捷

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> helper;
        for(int i=0;i<nums.size();i++){
            auto it = helper.find(target - nums[i]);
            if(it != helper.end()){
                res.push_back(it->second);
                res.push_back(i);
            }else{
                helper[nums[i]]=i;
            }
        }
        return res;
    }
};

复杂度

时间复杂度：O（n）
空间复杂度：O（n）（哈希表的额外存储空间）

[Yachen-Guo]

思路

hashmap 储存nums以及index，并在储存的同时判断map中是否已经包含target-nums[i]，因为结果唯一，所以一旦遇到就直接return双方的index

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

[ivangin]

code：

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

[charlestang]

思路

使用 哈希 记住已经扫描过的数字，每遇到一个新数字 num，就在已经扫描过的数字里搜索 target - num，搜索复杂度是 O(1)

所以整体时间复杂度是 O(n)，空间复杂度是 O(n)

代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}

        for k,v in enumerate(nums):
            search = target - v
            idx = d.get(search, -1)
            if idx != -1:
                return [idx, k]
            else:
                d[v] = k
        return [-1, -1]

[zhiyuanpeng]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
         pool = {}
         for index, val in enumerate(nums):
            if val not in pool:
                pool[target-val] = index
            else:
                return [pool[val], index]

time O(N), space O(N)

[LannyX]

思路

Hash Map

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        Map<Integer, Integer> mp = new HashMap<>();
        for(int i = 0; i < n; i++){
            mp.put(nums[i], i);
        }
        for(int i = 0; i < n; i++){
            int num = target - nums[i];
            if(mp.containsKey(num) && mp.get(num) != i){
                return new int[]{i, mp.get(num)};
            }
        }
        return new int[]{-1, -1};
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[bigboom666]

思路

哈希表

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{i,(int)map.get(target - nums[i])};
            }else{
                map.put(nums[i],i);
            }
        }
         return null;
    }
}

[tongxw]

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

      return new int[] {-1, -1};
    }
}

[cszys888]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for idx in range(len(nums)):
            comp = target - nums[idx]
            if comp in hashmap:
                return [idx, hashmap[comp]]
            else:
                hashmap[nums[idx]] = idx

time complexity: O(N) space complexity: O(N)

[Tesla-1i]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        for i in range(len(nums)):
            n = nums[i]
            index = nums_map.get(n)
            if index is None:
                deviation = target - n
                nums_map[deviation] = i
            else:
                return [index,i]

[stackvoid]

思路

方法1 ：两层for 循环 暴力解决。 方法2：将数组元素都放到hashMap，用减法看两个元素是否都在HASHMAP中。

代码(方法1)

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

代码(方法2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int[] ans = new int[2];
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            Integer index = hashMap.get(target - nums[i]);
            if (Objects.nonNull(index) && i != index) {
                ans[0] = i;
                ans[1] = index;
            }
        }
        return ans;
    }
}

算法分析

方法1：时间复杂度 O(N^2); 空间复杂度O(1)

方法2：时间复杂度 O(N); 空间复杂度O(N)

[aladingzl]

思路

利用哈希表

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map();
    for(let i = 0; i < nums.length; i++) {
        if(map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i];
        } else {
            map.set(nums[i], i);
        }
    }
    return [];
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[falconruo]

思路: 使用hashmap存放数组的值和indices

复杂度分析: 时间复杂度: O(n), n为数组nums的元素个数 空间复杂度: O(n), hashmap空间

代码(C++):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> used;
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            if (used.count(target - nums[i]))
                return {used[target - nums[i]], i};
            used[nums[i]] = i;
        }

        return {};
    }
};

[junbuer]

思路

哈希表

代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = dict()
        for i, num in enumerate(nums):
            if num in hashmap:
                return [hashmap[num], i]
            hashmap[target - num] = i    
        return []

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[Moin-Jer]

思路

---

哈希表

代码

---

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

复杂度分析

---

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[Myleswork]

思路

哈希表，可以边存边判断，问题不大

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> sec;
        for(int i = 0;i<nums.size();i++) sec.emplace(nums[i],i);
        for(int i = 0;i<nums.size();i++){
            if(sec.find(target-nums[i]) != sec.end() && sec[target-nums[i]] != i){
                return {i,sec[target-nums[i]]};
            }
        }
        return {0};
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[xinhaoyi]

1. 两数之和

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

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

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

思路

先遍历一遍，用哈希表装着，再遍历第二遍，找结果

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //遍历两遍数组，第一遍把值-坐标存进hash，第二遍顺着遍历，找有没有所需的数对应的key
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        int[] res = new int[2];
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i){
                res[0] = i;
                res[1] = map.get(target - nums[i]);
                return res;
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

[ginnydyy]

Problem

https://leetcode.com/problems/two-sum/

Note

• Hashmap
  • return index, so cannot sort the array and use two pointers

Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums == null || nums.length < 2){
            return new int[]{};
        }

        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int toFind = target - nums[i];
            if(map.containsKey(toFind)){
                return new int[]{map.get(toFind), i};
            }
            map.put(nums[i], i);
        }

        return new int[]{};
    }
}

Complexity

• T: O(n). n is the lenght of array.
• S: O(n). extra space is required for the map.

[1149004121]

1. 两数之和

思路

如果采用暴力遍历，用两层循环，第一层定num1，第二层找num2 = target - num1，时间复杂度为N^2。以空间换时间，用哈希表将遍历的结果存储，可将时间复杂度降为N。

代码

    var twoSum = function (nums, target) {
        let hash = new Map();
        const len = nums.length;
        for(let i = 0; i < len; i++){
            let num1 = nums[i];
            let num2 = target - num1;
            if(hash.has(num2)) return [hash.get(num2), i];
            else hash.set(num1, i);
        }
    };

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(N)。

[ZZRebas]

思路

遍历数据，对每一个出现的 num 判断其另一半 target - num 是否也出现在数组中即可

代码(Python)

def fun2(nums,target):
    for i in range(len(nums)):
        if target-nums[i] in nums:
            print([i,nums.index(target-nums[i])])
            break

nums = [2, 7, 11, 15]
target = 9
fun2(nums,target)    #[0, 1]

复杂度分析

• 时间复杂度：O(N)，N为数组长度。
• 空间复杂度：

[Flower-F]

解题思路

哈希表

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i];
        }
        map.set(nums[i], i);
    }
};

复杂度

时间：O(N) 空间：O(N)

[zol013]

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]
        '''
        n = len(nums)
        hashmap = dict()
        for i in range(n):
            if target - nums[i] in hashmap:
                return [i, hashmap[target - nums[i]]]
            else:
                hashmap[nums[i]] = i

[wenlong201807]

代码块

var twoSum = function (nums, target) {
  let map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (Array.from(new Set(map.keys())).includes(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    } else {
      map.set(nums[i], i)
    }
  }
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[laofuWF]

hash table

for each n: key (target - n), value: i

look for n in visited hash table

time/space: O(N)

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: visited = {}

    for i, n in enumerate(nums):
        if n in visited:
            return [visited.get(n), i]
        visited[target - n] = i

[KevinWorkSpace]

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

[linyang4]

思路

1. 用map来存储nums, map的key存nums的值, map的value存nums的索引
2. 遍历nums, 对于nums中的每一项num, 只需要判断taget-num的值存不存在map中即可
   • 如果target和num的差值在map中能找到, 直接返回2个索引
   • 如果差值不在map中, 把num和num的索引存到map中

代码

const twoSum = (nums, target) => {
    const numMap = new Map()
    for(let i = 0; i < nums.length; i++) {
        const remain = target - nums[i] 
        if (numMap.get(remain) !== undefined) {
            return [i, numMap.get(remain)]
        }
        numMap.set(nums[i], i)
    }
}

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(n)

[shamworld]

var twoSum = function(nums, target) {
    for(let i=0;i<nums.length;i++){
        for(let j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                return [i,j];   
           }
        }
    }
};

[frgthyju]

哈希表存储，key为数组nums的值，value为数组nums的键

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> m = new HashMap<Integer,Integer>();
        for (int i=0;i<nums.length;i++){
            if (m.containsKey(target-nums[i])){
                return new int[]{m.get(target-nums[i]),i};
            }
            m.put(nums[i],i);
        }
        return new int[0];
    }
}

时间复杂度O(n)

空间复杂度O(n)

[ggohem]

思路：

可以依次枚举，暴力破解，但是时间复杂度是O(n^2)。

这种知道一个求另一个的的题可以用哈希表解决。

代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[0];
    }
}

时空复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[732837590]

class Solution { public int[] twoSum(int[] nums, int target) { int len = nums.length;

    for(int i = 0;i < len -1;i++ ){
        for(int j = i + 1;j<len;j++){
            if(nums[i] + nums[j] == target){
                return new int[]{i,j};
            }
        }
    }

    throw new IllegalArgumentException("No two sum solution");
}

}

[didiyang4759]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer>num_map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            int complement = target - nums[i];
            if(num_map.containsKey(complement)){
                return new int[] {num_map.get(complement),i};
            }
            num_map.put(nums[i],i);
        }

        throw new IllegalArgumentException("no match found!");

    }
}

[jiaqiliu37]

 hashmap = dict()
        for i in range(len(nums)):
            if target - nums[i] in hashmap:
                return [i, hashmap[target - nums[i]]]

            hashmap[nums[i]] = I

Time complexity O(n) Space complexity O(n)

[Serena9]

代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        table = dict()
        for i, element in enumerate(nums):
            if target - element in table:
                return [table[target - element], i]
            else:
                table[element] = i
        return []

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

[biaohuazhou]

思路

用哈希表来记录已经出现过的数字 遍历的时候再判断当前数字和已经出现的数字和是否为target

代码

        public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <nums.length ; i++) {
            if (map.containsKey(target-nums[i])){
                return new int[]{i,map.get(target-nums[i])};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }

复杂度分析 时间复杂度： On) n为数组长度 空间复杂度：O(n)为栈所需要的大小

[Tiquiero]

var twoSum = function(nums, target) {
  const mapTemp = new Map();
  for (let i = 0; i < nums.length; i++) {
    const val = target - nums[i];
    if (mapTemp.has(val)) {
      return [mapTemp.get(val), i];
    } else {
      mapTemp.set(num[i], i);
    }
  }
  return [];
}

[Toms-BigData]

【Day 19】两数之和

思路

建立一个哈希表，key为num中的值，value为num中的i，遍历添加，当hashTable[target-x]存在时，返回该值的value和i为ans

golang代码

func twoSum(nums []int, target int) []int {
    hashTable := map[int]int{}
    for i, x := range nums{
        if p, ok := hashTable[target-x];ok{
            return []int{p, i}
        }
        hashTable[x] = i
    }
    return nil
}

复杂度

时间:O(n) 空间:O(n)

[ywang525]

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: h = {} for i in range(len(nums)): if target - nums[i] not in h: h[nums[i]] = i else: return [h[target-nums[i]], i]

[Zhang6260]

JAVA版本

该题可以使用暴力的方式，不过时间复杂度为n方，可以使用hash的方式，【注意，不能使用双指针，使用双指针的话，元素的数据的位置会发生变化。。。，】

class Solution {
    public int[] twoSum(int[] arr, int targer) {
        if(arr==null||arr.length==0)return arr;
       HashMap<Integer,Integer> map=new HashMap<>();
        int []res=new int[2];
        for(int i=0;i<arr.length;i++){
            if(map.containsKey(targer-arr[i])){
                res[0]=map.get(targer-arr[i]);
                res[1]=i;
                return res;
            }else {
                map.put(arr[i],i);
            }
        }
        return res;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

[now915]

map

var twoSum = function(nums, target) {
 let map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [i, map.get(target - nums[i])]
    }
    map.set(nums[i], i)
  }
};

• 时间复杂度 O(n)
• 空间复杂度 O(n)

[z1ggy-o]

思路

利用 hashtable 存放值和其 index，然后每次遇到一个新的值的时候，看看 table 里有没有对应的可以达成目标的值。

代码

CPP

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // store the remaind value and corresponding index into the map
        unordered_map<int, int> m; // <re, idx>

        for (int i = 0; i < nums.size(); i++) {
            int n = nums[i];
            int re = target - n;

            auto search = m.find(re);
            if (search != m.end()) {
                return {search->second, i};
            } else {
                m[n] = i;
            }
        }
        return {};
    }
};

复杂度分析

• 时间：O(n), 遍历 array
• 空间：O(n), 存放

[LuoXingbiao]

思路

使用HashMap, 按照模板即可。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] result = new int[2];
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                result[0] = i;
                result[1] = map.get(nums[i]);
                break;
            }
            map.put(target - nums[i],i);
        }

        return result;

    }
}

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

[Aobasyp]

思路 遍历数据，对每一个出现的 num 判断其另一半 target - num 是否也出现在数组中即可

public 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(nums[i] + nums[j] == target)
               return new int[]{i, j};

   return new int[]{-1, -1};
}

}

空间复杂度: O(1) 时间复杂度：O(n^2)

[liuajingliu]

解题思路

哈希表

代码实现

javaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const hashMap = new Map();
    for(let i = 0; i < nums.length; i++){
      if (hashMap.has(target - nums[i])) {
        return [hashMap.get(target - nums[i]), i]
      } else {
        hashMap.set(nums[i], i)
      }
    }
};

复杂度分析

• 时间复杂度 $O(N)$
• 空间复杂度 $O(N)$