S2
S2 copied to clipboard
halfrost
0001. Two Sum | LeetCode Cookbook
上述代码疑似没有考虑到 array 中有多个相同 value 的元素的情况。比如 [3, 3, 3, 5, 5, 5] 会输出 [2, 3], [2, 4] 和 [2, 5]，匹配结果不全。
@simonkuang938 上述代码疑似没有考虑到 array 中有多个相同 value 的元素的情况。比如 [3, 3, 3, 5, 5, 5] 会输出 [2, 3], [2, 4] 和 [2, 5]，匹配结果不全。
题目中只要求输出一组解即可。上面这个代码应该会输出 [2,3] 这组解。
算法训练的是思路，所以思路上为何没有考虑单解、多解、无解，以及给定数组有重复数字的情况。 原来这里说了，没注意到： You may assume that each input would have exactly one solution, and you may not use the same element twice.
@m3shine 算法训练的是思路，所以思路上为何没有考虑单解、多解、无解，以及给定数组有重复数字的情况。 原来这里说了，没注意到： You may assume that each input would have exactly one solution, and you may not use the same element twice.
你说的这些单解、多解的情况，后面有一道题其实就有。因为加了这些条件以后，题目就变难了。包括重复数字的情况，也有。 另外输出上也加了限制，比如多解的情况要求去重输出，要求按下标出现顺序输出。这些都算是增加了难度。我在去重输出那里错了好多次，当时弄的我非常蛋疼，我印象很深刻。另外要按照下标出现次数顺序输出就需要增加一个标号，在回溯的过程中一直保留它，最终输出的时候按着标号输出。
map查找并不是O(1)复杂度，所以整体并不能算O(n)
@zeddit 关于 map 查找的时间复杂度，要具体的讲的话，要看每个语言的具体实现。每个语言实现略有区别，比如 C++ 和 Java，Java 不同版本也有不同。除去语言实现方面，还要看哈希是否冲突，冲突了以后如何解决的，这里涉及到装载因子的问题。面试的时候如果简单的说，可以说是 O(1)复杂度，如果面试官真的要深究，那可以按照我这里说的，一点一点的和他细致的聊。
@halfrost
我竟然想到了量子力学
@yungson 为啥？🤔
我开了个比较大的脑洞哈哈，两个数组成一个数就好像两个数在纠缠一样，不是你先出现就是我先出现，不太严谨啦～
@yungson 厉害了，确实有点这种感觉~
评论区学习打卡！最开始的做法采用双循环的方式！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;
}
}
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
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)
@zeddit map查找并不是O(1)复杂度，所以整体并不能算O(n)
java中map查找key可以认为是O(1)， 查找value就肯定不是了，所以注意是查找value还是查找key
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;
}
}
# 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;
}
#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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？
if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？
@brness 可以直接用 value。只是我当时写的时候写成这样了。😅
@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？
有点不明白这个是什么意思？可以解释一下吗？
@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？
有点不明白这个是什么意思？可以解释一下吗？
@kyhong2000-dev 他的意思是，让我直接用 value，不检查 map 中是否存在这个 key。我想了想，他说的也不对，如果没有这个 key，就代表没有找到另外一半。
@halfrost
@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？
有点不明白这个是什么意思？可以解释一下吗？
@kyhong2000-dev 他的意思是，让我直接用 value，不检查 map 中是否存在这个 key。我想了想，他说的也不对，如果没有这个 key，就代表没有找到另外一半。
- 你这做法 Java里的 map.containsKey(target-nums[i]）对吧？直接检查create 的 map里面有没有符合另外一个nums的key
2.还有另外一个问题，你这个if里面的underscore是拿来做什么用的？我有点不太明白
@halfrost
@brness if _, ok := m[another]; ok { return []int{m[another], i} } 这里为什么不直接使用value，而是用_表示，在后面获取的时候又要使用m[another]？
有点不明白这个是什么意思？可以解释一下吗？
@kyhong2000-dev 他的意思是，让我直接用 value，不检查 map 中是否存在这个 key。我想了想，他说的也不对，如果没有这个 key，就代表没有找到另外一半。
- 你这做法 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 的值。
@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
