LeetCode上的Two Sum

Question

我正在尝试解决一道LeetCode的问题：

给定一个整数数组，找到两个数字使它们加起来等于特定目标数字。

函数twoSum应该返回这两个数字的索引，以便它们加起来等于目标数字，其中index1必须小于index2。请注意，你返回的答案（index1和index2）不是基于0的。

你可以假设每个输入都只有一个解。

输入: numbers={2, 7, 11, 15}, target=9 输出: index1=1, index2=2

第一次尝试使用了两个for循环，导致时间复杂度为O(n^2)，遗憾的是没有通过测试。因此我尝试使用：

target - current = index

搜索字典中是否存在该索引。

以下是我的代码：

class Solution:
    def twoSum(self, nums, target):
        dic = {}

        #A number can appear twice inside the same index, so I use a list
        for i in xrange(0, len(nums)):
            try:
                dic[nums[i]].append(i)
            except:
                dic[nums[i]] = []
                dic[nums[i]].append(i)

        try:
            for items_1 in dic[nums[i]]:
                for items_2 in dic[target-nums[i]]:
                    if(items_1+1 != items_2+1):
                        l = []
                        if(items_2+1 > items_1+1):
                            l.append(items_1+1)
                            l.append(items_2+1)
                        else:
                            l.append(items_2+1)
                            l.append(items_1+1)
                        return l
        except:
            pass

我在本地开发时，使用了LeetCode所提供的一个测试用例：[-3,4,3,90], 0，能够得到正确的结果[1, 3]，但在LeetCode上运行却返回了null。请问这是为什么？

- user1157751

---

一个数字在nums列表中出现两次真的很重要吗？重要的是你能得到一个索引，对吧？ - Shashank

嗯...如果数字是[0, 3, 4, 0]，正确的值应该是第1个和第4个索引。然而，由于0索引已经在第1个索引处，所以导致第4个索引不在字典中。 - user1157751

你想让我展示一下我会如何编写它吗？ - Shashank

@user1157751 是的，但他们使用的是哪个版本？我不熟悉LeetCode。 - Shashank

你在 try 部分中使用了 nums[i]，好像 i 在那里仍然有意义... - Stefan Pochmann

Answer 1

def twosum(nums=(6, 7, 11, 15, 3, 6, 5, 3), target=6):
    lookup = dict(((v, i) for i, v in enumerate(nums)))
    return next(( (i+1, lookup.get(target-v)+1) 
            for i, v in enumerate(nums) 
                if lookup.get(target-v, i) != i), None)

我没有进行详尽的测试，但基本逻辑应该是正确的。此算法可以分为两个阶段：

1. 为nums中的所有索引、值对创建一个值-索引字典。请注意，您可以拥有多个具有不同索引的值。在这种情况下，最高索引将存储在字典中，并且较低的索引将被覆盖。当然，可以修改此行为，但我认为对于此问题不需要修改，因为问题陈述的一部分是：“你可以假设每个输入都只有一个解。”因此，每个输入都有一个唯一的输出，因此我们永远不必担心返回“错误”的索引对。

2. 循环枚举nums，获取i作为索引，v作为值。检查我们创建的字典中是否有target-v的键，并同时断言该键指向的值不是 i。如果这是真的，请返回元组i +1，lookup.get（target-v）+1 。

- Shashank

---

为什么我的代码没有被接受呢？:( 它给出了完全相同的答案。 - user1157751

@user1157751 不好意思，我不知道。你的代码是否与我的具有相同的基本逻辑？细微差别很重要，例如处理项目的顺序等。 - Shashank

顺便说一下，我注意到你的逻辑是 目标 - 当前 = 索引，实际上应该是 目标 - 当前 = 与当前不同索引的值。也许这就是问题所在。 - Shashank

@PaulCornelius 请注意：“您可以假设每个输入都有恰好一个解决方案。”我明确说明字典将值更新为它们的最高索引。这就是为什么我的解决方案给出了（4,8）的原因。示例只是展示第一行的行为。即使该句子不在问题陈述中，我的答案仍然是正确的，因为（4,8）是指向总和为目标的值的有效索引对。 - Shashank

@PaulCornelius 我注意到我的答案有一个错误，就是没有给出单个索引对。现在已经修正了。 - Shashank

Answer 2

你想要的是以下这样的内容：

您需要类似以下的东西：

#! python3

def two_sum(arr,targ):
    look_for = {}
    for n,x in enumerate(arr,1):
        try:
            return look_for[x], n
        except KeyError:
            look_for.setdefault(targ - x,n)

a = (2,7,1,15)
t = 9
print(two_sum(a,t))  # (1,2)

a = (-3,4,3,90)
t = 0
print(two_sum(a,t))  # (1,3)

在需要的时候，您可以建立一个值字典。该字典以您寻找的值为键，并且对于每个值，您要跟踪其第一次出现的索引。只要找到满足问题的值，就完成了。只有一个for循环。

唯一的其他细节是将每个索引加1，以满足索引必须基于1的荒谬要求。好像这会教你Python编程一样。

使用setdefault函数向字典添加键，因为如果已经存在该键，则要保留它的值（最低索引）。

- Paul Cornelius

---

a=(2,7,1,15)，t=9，则输出为（0,1）。 - Vaishali Shinde

我简直不敢相信这个问题在七年和十五个赞之后还没有被注意到，所以我再次运行了程序以确保。它确实打印出（1,2），所以你一定是做错了什么。你是否忘记将索引加1？ - Paul Cornelius

Answer 3

我刚刚通过了以下代码。利用字典和注释只有一个解决方案的优势。将目标数查找在保存数字的查找字典中逐一保存数字。这种方法可以节省空间，并在nums中存在两个相同值时防止索引覆盖。

def twosum(self, nums, target):
    lookup = {}
    for cnt, num in enumerate(nums):
        if target - num in lookup:
            return lookup[target-num], cnt
        lookup[num] = cnt            

- Iris

Answer 4

这个答案使用零起点索引，因为这是索引的常规方式，而不是以一为基础的索引。它还使用了描述性变量名称，并且是为了易于理解而编写的。

from typing import List, Tuple

def twosum_indices_linear(nums: List[int], target: int) -> Tuple[int, int]:
    numtoindexmap = {}
    for num1_index, num1 in enumerate(nums):
        num2 = target - num1
        try:
            num2_index = numtoindexmap[num2]
        except KeyError:
            numtoindexmap[num1] = num1_index  
            # Note: Use `numtoindexmap.setdefault(num1, num1_index)` instead for lowest num1_index.
        else:
            return tuple(sorted([num1_index, num2_index]))

例子：

print(twosum_indices_linear([2, 7, 11, 15], 9))
(0, 1)

print(twosum_indices_linear([3, 3], 6))
(0, 1)

print(twosum_indices_linear([6, 7, 11, 15, 3, 6, 5, 3], 6))
(4, 7)

信用：joeg的答案

- Asclepius

Answer 5

我的一行解决方案：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res=[[nums.index(val),nums[ind +1:].index(target-val)+ ind +1] for ind,val in enumerate(nums) if target -val in nums[ind +1:]]
        return res[0]

我可以解释一下，如果有人感兴趣的话 :)

- Arshad

---

你应该主动添加解释（无需等待他人提问）。这会让你的回答更好，并且更有可能获得点赞。请记住，不要改变原意。 - Adrian Mole

你必须解释你的答案。 - Willy satrio nugroho

Answer 6

public static int[] twoSum1(int[] nums, int target) 
{
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<>();

 
    for(int i=0; i<nums.length; i++)
        map.put(nums[i],i);
    
    
    for(int i=0; i<nums.length; i++)
    {
        int index = i;
        int anotherValue = target-nums[index];
        
        if(map.get(anotherValue)!=null && map.get(anotherValue)!=i)
        {
            result[0] = index;
            result[1] = map.get(target-nums[index]);
            
            System.err.println("result[0]: " + result[0]);
            System.err.println("result[1]: " + result[1]);
            
            return result;
        }
    }        
    return result;
}

- Maverick King

Answer 7

如果有人仍在寻找与此问题相关的JavaScript解决方案，

/** 
1. Two Sum

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].
* */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  const numsObjs = {}; // create nums obj with value as key and index as value eg: [2,7,11,15] => {2: 0, 7: 1, 11: 2, 15: 3}

  for (let i = 0; i < nums.length; i++) {
    const currentValue = nums[i];

    if (target - currentValue in numsObjs) {
      return [i, numsObjs[target - currentValue]];
    }
    numsObjs[nums[i]] = i;
  }

  return [-1, -1];
}

console.log(twoSum([3,7,3], 6))

- Keshan Nageswaran

---

但这里使用了相同的元素两次。你有多个对nums的引用。 - Steven Matthews

Answer 8

一趟哈希表

这可以在一趟中完成。怎么做？ 好吧，在迭代并将元素插入哈希表时，它还应该向后查找以检查当前元素的补码是否已经存在于哈希表中。如果存在，则我们已经找到了解决方案并立即返回。

复杂度：

时间复杂度：O(n)。我们只遍历包含n个元素的列表一次。每次在表中查找只需要O(1)的时间。

空间复杂度：O(n)。所需的额外空间取决于存储在哈希表中的项目数，最多存储n个元素。

const nums = [1, 2, 4, 6, 7, 11, 15]
const target = 9


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
    const map = new Map()
    
    const l = nums.length
    for (var i = 0; i < l; i++) {
        const complement = target - nums[i]
        if (map.has(complement)) return [map.get(complement), i]
        
        map.set(nums[i], i)
    }
    
    throw new Error('No two sum solution')
}

const [a, b] = twoSum(nums, target)

const addendA = nums[a]
const addendB = nums[b]
console.log({addendA, addendB})

- Teocci

Answer 9

这是我的答案

class Solution:
    def twoSum(self, nums, target):
        ls = []
        for i in range(0, len(nums)):
            item = target - nums[i]
            nums[i] = "done"
            if item in nums:
                if i != nums.index(item):
                    ls.append(i)
                    ls.append(nums.index(item))
                    return ls

- Mohamed Abu ElGheit

---

在数组为[3,2,4]，目标值为6的情况下，该程序失败了。它返回的是[0,0]，但期望的结果是[1,2]。 - casillas

Answer 10

这个答案是内存高效的，因为它使用了列表弹出方法，但花费更长的时间

class Solution:   
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        while len(nums)>0:
            ind = len(nums)-1
            item = nums.pop()
            if target-item in nums:
                return [ind, nums.index(target-item)]

- Itachi