0001. Two Sum | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0001.Two-Sum/

[simonkuang938]

上述代码疑似没有考虑到 array 中有多个相同 value 的元素的情况。比如 [3, 3, 3, 5, 5, 5] 会输出 [2, 3], [2, 4] 和 [2, 5]，匹配结果不全。

[halfrost]

@simonkuang938 上述代码疑似没有考虑到 array 中有多个相同 value 的元素的情况。比如 [3, 3, 3, 5, 5, 5] 会输出 [2, 3], [2, 4] 和 [2, 5]，匹配结果不全。

题目中只要求输出一组解即可。上面这个代码应该会输出 [2,3] 这组解。

[freiegeister]

算法训练的是思路，所以思路上为何没有考虑单解、多解、无解，以及给定数组有重复数字的情况。 原来这里说了，没注意到： You may assume that each input would have exactly one solution, and you may not use the same element twice.

[halfrost]

@m3shine 算法训练的是思路，所以思路上为何没有考虑单解、多解、无解，以及给定数组有重复数字的情况。 原来这里说了，没注意到： You may assume that each input would have exactly one solution, and you may not use the same element twice.

你说的这些单解、多解的情况，后面有一道题其实就有。因为加了这些条件以后，题目就变难了。包括重复数字的情况，也有。 另外输出上也加了限制，比如多解的情况要求去重输出，要求按下标出现顺序输出。这些都算是增加了难度。我在去重输出那里错了好多次，当时弄的我非常蛋疼，我印象很深刻。另外要按照下标出现次数顺序输出就需要增加一个标号，在回溯的过程中一直保留它，最终输出的时候按着标号输出。

[xujunhai]

这个空间复杂度 也O(n)啦吧

[halfrost]

这个空间复杂度 也O(n)啦吧

@xujunhai 嗯。是的。

[zeddit]

map查找并不是O(1)复杂度，所以整体并不能算O(n)

[halfrost]

map查找并不是O(1)复杂度，所以整体并不能算O(n)

@zeddit 关于 map 查找的时间复杂度，要具体的讲的话，要看每个语言的具体实现。每个语言实现略有区别，比如 C++ 和 Java，Java 不同版本也有不同。除去语言实现方面，还要看哈希是否冲突，冲突了以后如何解决的，这里涉及到装载因子的问题。面试的时候如果简单的说，可以说是 O(1)复杂度，如果面试官真的要深究，那可以按照我这里说的，一点一点的和他细致的聊。

[halfrost]

我竟然想到了量子力学

@yungson 为啥？🤔

[halfrost]

@halfrost

我竟然想到了量子力学

@yungson 为啥？🤔

我开了个比较大的脑洞哈哈，两个数组成一个数就好像两个数在纠缠一样，不是你先出现就是我先出现，不太严谨啦～

@yungson 厉害了，确实有点这种感觉~

[WSharkCoder]

评论区学习打卡！最开始的做法采用双循环的方式！O(n^2)

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

[koilin]

都是go语言写的吗

[halfrost]

@koilin 是的。全部都是 Go 写的。纯 Go 的

[chiyoi]

python，求问这是O(n)吗:

nums = [int(x) for x in input("Given nums = ").split()]
target = int(input("target = "))
dic = {}
for idx, num in enumerate(nums):
    dic[num] = (idx, num)
for idx, num in enumerate(nums):
    if idx1_ := dic.get(target - num):
        print("return [{0}, {1}]".format(idx, idx1_[0]))
        break

[halfrost]

python，求问这是O(n)吗:

nums = [int(x) for x in input("Given nums = ").split()]
target = int(input("target = "))
dic = {}
for idx, num in enumerate(nums):
    dic[num] = (idx, num)
for idx, num in enumerate(nums):
    if idx1_ := dic.get(target - num):
        print("return [{0}, {1}]".format(idx, idx1_[0]))
        break

@CHIYOI 是O(n)

[sunday2]

@zeddit map查找并不是O(1)复杂度，所以整体并不能算O(n)

java中map查找key可以认为是O(1)， 查找value就肯定不是了，所以注意是查找value还是查找key

[chen-gongzhe]

Java打卡1. 两数之和

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

[alan1914]

# java
public int[] twoSum(int[] nums, int target) {

        int length = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp) && map.get(temp) != i) {
                return new int[]{map.get(temp), i};
            }
            map.put(nums[i], i);
        }

        return null;
    }

[luommy]

golang 不知名菜鸡

func twoSum(nums []int, target int) []int { for i:=0;i <len(nums);i++{ for m:=i+1;m<len(nums);m++{ if nums[i]+nums[m]==target{ return []int{i,m} } } } return nil }

作者：clever-elgamalzfl 链接：https://leetcode-cn.com/problems/two-sum/solution/by-clever-elgamalzfl-bgpn/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[brness]

if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？

[halfrost]

if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？

@brness 可以直接用 value。只是我当时写的时候写成这样了。😅

[kyhong2000-dev]

@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？

有点不明白这个是什么意思？可以解释一下吗？

[halfrost]

@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？

有点不明白这个是什么意思？可以解释一下吗？

@kyhong2000-dev 他的意思是，让我直接用 value，不检查 map 中是否存在这个 key。我想了想，他说的也不对，如果没有这个 key，就代表没有找到另外一半。

[kyhong2000-dev]

@halfrost

@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？

有点不明白这个是什么意思？可以解释一下吗？

@kyhong2000-dev 他的意思是，让我直接用 value，不检查 map 中是否存在这个 key。我想了想，他说的也不对，如果没有这个 key，就代表没有找到另外一半。

1. 你这做法 Java里的 map.containsKey(target-nums[i]）对吧？直接检查create 的 map里面有没有符合另外一个nums的key

2.还有另外一个问题，你这个if里面的underscore是拿来做什么用的？我有点不太明白

[halfrost]

@halfrost

@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？

有点不明白这个是什么意思？可以解释一下吗？

@kyhong2000-dev 他的意思是，让我直接用 value，不检查 map 中是否存在这个 key。我想了想，他说的也不对，如果没有这个 key，就代表没有找到另外一半。

1. 你这做法 Java里的 map.containsKey(target-nums[i]）对吧？直接检查create 的 map里面有没有符合另外一个nums的key

2.还有另外一个问题，你这个if里面的underscore是拿来做什么用的？我有点不太明白

@kyhong2000-dev

上面那个同学说“不直接使用 value”，应该是下面👇🏻这段代码的意思，我上一条回复你的内容有点问题。

if v, ok := m[another]; ok {
    return []int{v, i}
}

关于你这 2 个问题，问题 1，你的理解是正确的。问题 2，我的原有写法中，没有用到 underscore ，underscore 在 go 语法中指的是忽略这里的值。如果不使用 underscore，写法见上面我这一小段代码，underscore 的位置其实是 map 中 value 的值。

[fushuzaishan]

@chiyoi python，求问这是O(n)吗:

nums = [int(x) for x in input("Given nums = ").split()]
target = int(input("target = "))
dic = {}
for idx, num in enumerate(nums):
    dic[num] = (idx, num)
for idx, num in enumerate(nums):
    if idx1_ := dic.get(target - num):
        print("return [{0}, {1}]".format(idx, idx1_[0]))
        break

虽然能得到答案，在[5,3,3,3,3,3]的情况得到的答案是0，5