【Day 19 】2021-09-28 - 两数之和

[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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[alwaysbest]

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>((int) ((float) nums.length / 0.75F + 1.0F)); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])) { return new int[]{map.get(target - nums[i]), i}; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum value"); } }

[last-Battle]

思路

关键点

• 哈希

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int, int> um;

        for (int i = 0; i < nums.size(); ++i) {
            if (um.find(target - nums[i]) != um.end()) {
                return vector<int>{um[target - nums[i]], i};
            }

            um[nums[i]] = i;
        }

        return res;
    }
};

复杂度分析

令 n 为数组长度。

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

[yanglr]

思路

可以用双指针或哈希表来做。

方法1: 双指针法

先固定一个, 找另一个。发现第一次出现nums[i] + nums[j] == target就返回结果.

代码

实现语言: C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {        
        vector<int> res(2);
        // 双指针, 先固定一个
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = i + 1; j < nums.size(); j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }
};

复杂度分析:

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

方法2: 哈希表

在哈希表中找 target - 当前循环变量i对应的那个数。哈希表存储每个数对应的下标(映射: value -> index)。

代码

实现语言: C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> dict; // map: value -> index
        vector<int> res(2);
        for (int i = 0; i < nums.size(); i++)
        {
            int query = target - nums[i];
            if (dict.find(query) == dict.end())
                dict[nums[i]] = i;
            else
            {
                res[0] = dict[query]; // 如果能找到, query会出现在nums[i]的前面(index of query <= i)
                res[1] = i;
                return res;
            }
        }
        return {};
    }
};

复杂度分析:

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

[ZhuMengCheng]

思路,判断差值,存储 hash判断是否存在

var twoSum = function(nums, target) {
    // 定义map存储差值    
    let map = new Map();
    for(let i =0;i<nums.length ;i++){
        // 计算差值
        const value = target - nums[i];
        if(map.has(value)){
            // 存在即返回当前存储差值的下标,和当前值的下标
            return [map.get(value), i];
        }else{
            // 存储所有差值的下标
            map.set(nums[i], i)
        }
    }
};

// 空间复杂:O(N) // 时间复杂:O(N)

[yachtcoder]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        m = {}
        for i, n in enumerate(nums):
            if target - n in m:
                return [m[target - n], i]
            m[n] = i
        return [-1, -1]

[BpointA]

思路

哈希表+遍历数组。

Python3代码

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

复杂度

时间复杂度：O(n) ，遍历数组，对遍历过的数查询哈希表

空间复杂度：O(n) ，哈希表最长为数组长度

[Kirito1017]

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.containsKey(target - nums[i])) {
                res[0] = map.get(target - nums[i]);
                res[1] = i;
                return res;
            }
            map.put(nums[i], i);
        }

        return res;
    }
}

[yibenxiao]

【Day 19】两数之和

思路

遍历整个列表，当前值为x，寻找y=target-x

代码

class Solution:
    def twoSum(self,nums,target):
        n = len(nums)
        for x in range(n):
            a = target - nums[x]
            if a in nums:
                y = nums.index(a)
                if x == y: 
                    continue
                else:
                    return x,y 

复杂度

时间复杂度：O(N*LogN)

空间复杂度：O(1)

[kidexp]

thoughts

Hashmap key是值 value存下标，然后遍历一遍，看sum-nums[i]在不在之前的hashmap里面，在就返回，不在就加入hashmap继续

code

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

complexity

time O(n) Space O(n)

[wangzehan123]

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

        for (int i = 0; i < numbers.length; i++) {
            if (map.get(numbers[i]) != null) {
                int[] result = {map.get(numbers[i]), i};
                return result;
            }
            map.put(target - numbers[i], i);
        }

        int[] result = {};
        return result;
    }
}

复杂度分析

令 n 为数组长度。

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

[jaysonss]

思路

构建一个哈希表dict，遍历数组，尝试获取补数索引

关键点˜

• 无

代码

• 语言支持：Java

Java Code:

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

复杂度分析

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

[st2yang]

思路

• hash table

代码

• python

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

复杂度

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

[Okkband]

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

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

[zjsuper]

idea: Using dic to store the value and index Time and space: O(N)

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

[taojin1992]

Plan:

bruteforce: two pointers O(n^2) time with O(1) space

optimized:
traverse, search for target - val in map, if no then insert into map
val - index map

n = nums.length
Time: O(n)
Space: O(n) 

Code:

class Solution {
    // bruteforce
    public int[] twoSum1(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[]{};
    }

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

[pangjiadai]

思路：Hashmap

空间换时间

Python3

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

复杂度

• 时间：O(n)
• 空间：O(n)

[leungogogo]

LC1. Two Sum

Method 1. Map

Main Idea

Use a map to record the number we've seen so far, if map.get(k - nums[i]) != null, then we've found the pair.

Code

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

            map.put(nums[i], i);
        }

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

Complexity Analysis

Time: O(n)

Space: O(n)

Method 2. Sorting + 2 Ptrs

Main Idea

Sort the array, then perform two pointers find the pair:

• If nums[l] + nums[r] == tar, then this is the pair we need to find.
• If nums[l] + nums[r] < tar, then we need to increment l so the sum will be greater than current.
• Else, decrement r.

Note that we need to return the index, and if we sort the input then we no longer have access to the indices, so we need to create an index array arr to sort.

Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Integer arr[] = new Integer[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            arr[i] = i;
        }

        Arrays.sort(arr, (n1, n2) -> nums[n1] - nums[n2]);

        int l = 0, r = nums.length - 1;
        while (l < r) {
            if (nums[arr[l]] + nums[arr[r]] == target) {
                return new int[] {arr[l], arr[r]};
            } else if (nums[arr[l]] + nums[arr[r]] < target) {
                ++l;
            } else {
                --r;
            }
        }

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

Complexity Analysis

Time: O(nlogn)

Space: O(n)

[pzl233]

思路

用HashMap存储数组中每个元素和相对的index. 在遍历数组的同时寻找是否存在一个值可以使当前值 + 它 = target

代码

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

复杂度分析

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

[mmboxmm]

思路

第一题

代码

fun twoSum(nums: IntArray, target: Int): IntArray {
  val map = mutableMapOf<Int, Int>()
  for ((index, num) in nums.withIndex()) {
    if (map.containsKey(num)) return intArrayOf(map[num]!!, index)
    map[target - num] = index
  }
  return intArrayOf()
}

复杂度

• Time: O(n)
• Space: O(n)

[pophy]

思路

• 遍历数组时 把已经访问的数字放入map中
  • 遍历下一个数字时 如果发现 target - num在map中出现 则找到答案

Java Code

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

时间&空间

• 时间 O(n)
• 空间 O(n)

[erik7777777]

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};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

[q815101630]

Thoughts

利用哈希表，可以把当前数字存进表，遍历时，如果target-v在表内，说明之前存过，就return

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

Time: O(n) Space: O(n)

[cicihou]

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

[MonkofEast]

1. Two Sum

Click Me

Algo

INSIDE DNA

Code

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

Comp

T: O(N)

S: O(N)

[xj-yan]

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};
            }else {
                map.put(nums[i], i);
            }
        }
        return null;
    }
}

Time Complexity: O(n) Space Complexity: O(n)

[nonevsnull]

思路

• 拿到题的直觉解法
  • use hashmap

AC

代码

//use hashmap
class Solution {
    public int[] twoSum(int[] nums, int target) {
        //create map to save [visited, index]
        HashMap<Integer, Integer> map = new HashMap<>();
        //traverse nums
        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[2];
    }
}

复杂度

//use hashmap time: 需要遍历nums，O(N) space: 需要hashmap，O(N)

[ruohai0925]

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

# Hashtable 2
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[num] = i
        return []

# Similar to hashtable 2
def two_sum(nums, target):
    dct = {}
    for i, n in enumerate(nums):
        cp = target - n
        if cp in dct:
            return [dct[cp], i]
        else:
            dct[n] = i

复杂度分析

令 n 为数组长度。

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

[chakochako]

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

        for i, v in enumerate(nums):
            if (target - v) in d:
                return [d[target - v],i]
            else:
                d[v] = i

[falconruo]

思路:

使用hashmap存放数组的值和indices, 循环判断数组的每一个元素,如果target - nums[i]在hashmap中则nums[i]必在, 返回两者的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 {};
    }
};

[heyqz]

code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff not in hashmap:
                hashmap[num] = i
            else:
                return [hashmap[diff], i]

complexity

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

[JiangyanLiNEU]

Idea

• Use a dictionary call dic to store the original num-index, note that there might be repeated numbers in the array, so the value of dic should be []
• Sort the nums array and we can use two pointers - pointerA starts from 0, pointerB starts from the end
• Update two pointer based on the relationship between nums[pointerA]+nums[pointerB] and target, either increase pointerA or decrease pointerB
• when we get two numbers that adds up to target, we need check if those two numbers are the same: if they are the same, return dic[number] because there won't be 3 same elements, or the result won't be the only one Otherwise, we can get the index of those numbers and return it

Implement (Runtime=O(nlogn) Space=O(n))

class Solution(object):
    def twoSum(self, nums, target):
        # dic: num: cur_index
        dic = defaultdict(list)
        for index, num in enumerate(nums):
            dic[num].append(index)
        # order nums, two pointer to get right numbers
        nums.sort()

        first = 0
        second = len(nums)-1

        while nums[first] + nums[second] != target:
            if nums[first] + nums[second] > target:
                second -= 1
            elif nums[first] + nums[second] < target:
                first += 1
            else:
                break
        # return index with the help of dic
        if nums[first] == nums[second]:
            return dic[nums[first]]
        return [dic[nums[first]][0], dic[nums[second]][0]]

[comst007]

1. 两数之和

---

思路

哈希表。 通过哈希表记录当前已经出现的数及其下表。当遍历到每个数组元素cur_num时， 查一下sum - cur_num在不在哈希表中。

如果在说明存在两个数。否则不存在。

代码

• C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> h_cnt;
        int n, ii, jj;
        n = nums.size();
        if(n < 2) return vector<int>();

        vector<int> ans;
        h_cnt[nums[0]] = 0;
        for(ii = 1; ii < n; ++ ii){
            if(h_cnt.count(target - nums[ii])){
                jj = h_cnt[target - nums[ii]];
                ans.push_back(ii);
                ans.push_back(jj);
                break;
            }
            h_cnt[nums[ii]] = ii;
        }
        return ans;

    }
};

---

复杂度分析

n 为数组元素个数。

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

[potatoMa]

思路

---

哈希表储存差值

代码

---

JavaScript Code

/**
 * @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++) {
        const num = nums[i];
        if (!map.has(target - num)) {
            map.set(num, i);
            continue;
        }
        return [map.get(target - num), i];
    }
};

复杂度分析

---

时间复杂度：O(N)

空间复杂度：O(N)

[yingliucreates]

link:

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

代码 Javascript

const twoSum = function (nums, target) {
  let hash = {};

  for (let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if (hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
  return [];
};

复杂度分析

时间空间皆为 O(n)

[tongxw]

思路

哈希表记忆

代码

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

    return j == -1 ? [] : [i, j];
};

• TC: O(n)
• SC: O(h)

[Menglin-l]

思路：

用hashmap来做，key为值，value为索引，遍历数组，同时寻找target - num[i]，找到就返回。

---

代码部分：

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

        for (int i = 0; i < nums.length; i ++) {

            if (list.containsKey(target - nums[i])) {
                return new int[]{i, list.get(target - nums[i])};
            }

            list.put(nums[i], i); 
        }
        return new int[]{};
    }
}

---

复杂度：

Time: O(N)

Space: O(N)

[pan-qin]

idea: use a hashmap to tell whether target-nums[i] exists. If yes, return; else save the value and index into the map. Time: O(n) Space: O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = new int[2];
        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;
            }
            else {
                map.put(nums[i],i);
            }
        }
        return res;
    }
}

[skinnyh]

Note

Scan the list and use a dict to record each num and its idx. If (target - current_num) is in the dict then we find the result pair.

Solution

def twoSum(self, nums: List[int], target: int) -> List[int]:
    d = {}
    for idx, n in enumerate(nums):
        if (target - n) in d:
            return [d[target - n], idx]
        d[n] = idx

Time complexity: O(N)

Space complexity: O(N)

[itsjacob]

Intuition

• O(n) time and O(n) space solution with hashtables

Implementation

class Solution
{
public:
  vector<int> twoSum(vector<int> &nums, int target)
  {
    std::unordered_map<int, int> aMap;
    std::vector<int> res;
    for (int ii = 0; ii < nums.size(); ii++) {
      if (aMap.count(target - nums[ii]) > 0) {
        res.push_back(ii);
        res.push_back(aMap[target - nums[ii]]);
        break;
      } else {
        aMap.emplace(nums[ii], ii);
      }
    }
    return res;
  }
};

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

[thinkfurther]

思路

用dict记录每一个数的位置，然后判断target减去这个数是否在dict里

代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = dict()
        for idx, value in enumerate(nums):
            hashmap[value] = idx            
        for idx, value in enumerate(nums):
            j = hashmap.get(target - value)
            if j != None and idx != j:
                return [idx,j]

复杂度

时间复杂度 ：O(N)

空间复杂度：O(N)

[zol013]

思路：遍历数组，查看target - nums[i] 在不在hashmap里面， 如果在的话 返回， 不在的话把nums[i]以及index记录在hashmap。\

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

Time Complexity: O(n) Space Complexity: O(n)

[ZiyangZ]

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])) {
                map.put(nums[i], i);
            } else {
                return new int[] {i, map.get(target - nums[i])};
            }
        }
        return null;
    }
}

[joeytor]

思路

一次遍历, 每次遇到一个数, 先判断 target - num 在不在哈希表中, 如果在的话说明找到了那两个整数, 返回这个数 和 target - num 的 index

如果 n 不在 d 中, 把 d[n] = i 添加到 dict 中

代码

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

复杂度

N 是 nums 长度

时间复杂度: O(N) 一次遍历数组

空间复杂度: O(N) 哈希表最坏情况是 O(N) 级别复杂度

[kennyxcao]

1. Two Sum

Intuition

• Use a hashmap to store seen nums

Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
  const lookup = {};
  for (let i = 0; i < nums.length; ++i) {
    const j = lookup[target - nums[i]];
    if (j != null) return [i, j];
    lookup[nums[i]] = i;
  }
  return [-1, -1];
};

Complexity Analysis

• Time: O(n)
• Space: O(n)
• n = len(nums)

[Yufanzh]

Intuition

Two sum can be solved by storing the value in hash map which will make lookup much faster.

Algorithm in Python3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashMap = collections.defaultdict(int)

        for i, num in enumerate(nums):
            if target-num in hashMap:
                return [i, hashMap[target-num]]
            else:
                hashMap[num] = i
        return -1

Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(n)

[shixinlovey1314]

Title:1. Two Sum

Question Reference LeetCode

Solution

Use a map to store the value and its index, while iterating the array, keep on checking if the counter part has been in the map already, and return results if so.

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::map<int, int> mapper;
        vector<int> result;

        for (int i = 0; i < nums.size(); i++) {
            int delta = target - nums[i];
            if (mapper.count(delta)) {
                result.push_back(mapper[delta]);
                result.push_back(i);
                break;
            }

            mapper[nums[i]] = i;
        }

        return result;
    }
};

Complexity

Time Complexity and Explanation

O(n), need to visit each item once

Space Complexity and Explanation

O(n), used to store in map.

[BlueRui]

Problem 1. Two Sum

Algorithm

• Use a map to keep values and indices of visited numbers.
• Iterate over the array. For each nums[i], check if target - nums[i] is in the map. If not, add nums[i] and its index to the map. If yes, we found our solution.

Complexity

• Time Complexity: O(N).
• Space Complexity: O(N).

Code

Language: Java

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

[james20141606]

Day 19: 1. Two Sum (hashtable, two pointers)

• Problem Link

  • 1. Two Sum

• Ideas

  • It is a very classic problem and the very first question of leetcode. We could brute forcefully solve the problem using O(n^2) time and O(1) space. Or we could save a hash table and use O(N) time and space complexity

• Complexity:

  • Time: O(N)
  • Space: O(N)

• Code

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

• other resources:

[Mahalasu]

思路

经典题，用hashmap

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

        return []

T: O(N) S: O(N)

[naivecoder-irl]

思路

哈希表，查询到结果则返回，查询不到则插入。

代码

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]; //key point
            if (map.containsKey(diff)){
                return new int[]{map.get(diff), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

复杂度分析

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