{1,6,3,2,5}中找到两个数的和为11

刚开始学习leetcode。这是leetcode的第一题。https://leetcode.com/problems/two-sum/
请问下面两个答案，你更喜欢哪一个？他俩是等价的吗？
这个map.find 不也是一个循环吗？我认为这两个答案其实是一样的。答案A可能速度更快。
请高手解答。

有人认为A是O(n^2)。 所以A不是正确答案。请赐教A到底是正确的答案，还是错误的。
A和B的complexity是不是一样的？
为什么A的实际运算速度快于B？


v = {1, 6, 3, 2, 5};
target = 11；


A）
vector<int> twoSum(vector<int>& nums, int target) {     int a=0;     int b=0;     for(int ii=0;ii<nums.size()-1;ii++)     {       for(int j=i+1;j<nums.size();j++)       {         if(nums[ii]+nums[j]==target)         {           a=ii;           b=j;         }       }     }     return {a,b};   }
 B）
  vector<int> twoSum(vector<int> &nums, int target)   {     map<int, int> m;     vector<int> v;     int n = nums.size();     for (int i = 0; i < n; i++)     {
      int diff = target - nums;       if (m.find(diff) != m.end())       {         auto p = m.find(diff);         v.push_back(p->second);         v.push_back(i);       }       m.insert(make_pair(nums, i));     }
    return v;   }

if(nums+nums[j]==target)
这一行明显错误吧

if(nums+nums[j]==target)
这一行明显错误吧
welkin25 发表于 2022-08-02 16:45

更正了。nums + nums[j] == target

你这A和B不是完全一样的code吗 没看出来有啥差别 另外if（nums 有bug 应该是nums【i】（这里之前用英文的中括号打了显示不出来）这个做法是n^2 时间复杂度太高 可以用hash表做 /看看leetcode discussion里的答案 2sum方法蛮多的
没仔细对比两code
lz你如果刚入门给你推荐一个 neetcode 150道核心题 youtube有视频 从题目分析 思路解析 到coding

没看你具体代码 但看到two sum 哈希表查找是constant 不知道你是问这个吗？

你这A和B不是完全一样的code吗 没看出来有啥差别 另外if（nums 有bug 应该是nums 这个做法是n^2 时间复杂度太高 可以用hash表做 /看看leetcode discussion里的答案 2sum方法蛮多的
gogomeowmeow 发表于 2022-08-02 16:49

请问B的map是不是你说的hash表？
你认为A和B是一样的？
B大家觉得是标准答案。也就是说B是正确的。
现在的问题是，A到底正确不正确。我个人认为A也是对的。 A和B的时间复杂度 都 小于 O(n^2).

能不能把代码写利索了再贴上来，B这段代码肯定不能跑啊
PS已经找到了为什么还要跑完循环，直接return就好了。这样的代码真是看得窒息

请问B的map是不是你说的hash表？
你认为A和B是一样的？
B大家觉得是标准答案。也就是说B是正确的。
现在的问题是，A到底正确不正确。我个人认为A也是对的。 A和B的时间复杂度 都 小于 O(n^2).
gooog 发表于 2022-08-02 16:52

而且有必要问正不正确吗，你按照A的思路写好提交，过了就是正确的

你的基础需要去补一补，hash list set heap 等的实现，时间空间复杂度，以及普通的时间空间复杂度，上来就刷题没啥用，需要系统学一下

map find的complexity不是n

回复 6楼gooog的帖子
A哪里小于n2？就是n2啊

map find的complexity不是n
shoon_yee 发表于 2022-08-02 16:58

多谢！ 我们可以认为 答案A的第二个循环 complexity也不是n 吗？ for(int j=i+1;j<nums.size();j++)

回复 6楼gooog的帖子
A哪里小于n2？就是n2啊
wfmlover 发表于 2022-08-02 16:59

这就是我的问题。大家都和你一样认为A是n^2.
我觉得A里面的第二个循环并没有循环n次。 for(int j=i+1;j<nums.size();j++) 所以答案A的复杂度应该是小于n^2的。
另外，实际程序运行的时间，A要快于B.

能不能把代码写利索了再贴上来，B这段代码肯定不能跑啊
PS已经找到了为什么还要跑完循环，直接return就好了。这样的代码真是看得窒息
welkin25 发表于 2022-08-02 16:55

B是标准答案。leetcode可以提交的。
正确无疑。
你再测试一下。
B没有问题。有问题的是A。为什么A不能被leetcode接收为正确答案。 实际中，A比B的速度还快。

没想到有一天我会在华人上刷leetcode…… 因为你code的排版太伤眼睛了，所以我没有细看你code的内容。hashMap查找不是循环，hashmap如果没有遇到严重的collision查找的速度是O(1)，所以如果for loop里套map.find()肯定比for loop里套for loop更快。 two sum 如果用暴力解法，也就是你的答案A时间复杂度是O(n^2) 用哈希表，时间复杂度是O（n） 这题还可以用binary search做，就是一层for loop里套一个复杂度为O（logn）的查找总时间复杂度O（nlogn）
补充：刚没细看，仔细一看你这用的不是哈希表啊，是map呀

没想到有一天我会在华人上刷leetcode…… 因为你code的排版太伤眼睛了，所以我没有细看你code的内容。hashMap查找不是循环，hashmap如果没有遇到严重的collision查找的速度是O(1)，所以如果for loop里套map.find()肯定比for loop里套for loop更快。 two sum 如果用暴力解法，也就是你的答案A时间复杂度是O(n^2) 用哈希表，也就是你的解法B，时间复杂度是O（n） 这题还可以用binary search做，就是一层for loop里套一个复杂度为O（logn）的查找总时间复杂度O（nlogn）

苏小鬟 发表于 2022-08-02 17:06

多谢！我再去学习学习。 这个hash table 是O（1），好难琢磨啊。

多谢！我再去学习学习。 这个hash table 是O（1），好难琢磨啊。
gooog 发表于 2022-08-02 17:21

建议先补一下基本的数据结构，不要只是一味刷题。这样你就不会问这些问题了， 另外建议有时间多看看别人优化过的代码，看多了自己写的代码也会好很多。

这不就是2sum变种吗？ 有这么复杂吗？ 还聊了2页多

楼主基础太差 乱搅和一通

没想到有一天我会在华人上刷leetcode…… 因为你code的排版太伤眼睛了，所以我没有细看你code的内容。hashMap查找不是循环，hashmap如果没有遇到严重的collision查找的速度是O(1)，所以如果for loop里套map.find()肯定比for loop里套for loop更快。 two sum 如果用暴力解法，也就是你的答案A时间复杂度是O(n^2) 用哈希表，也就是你的解法B，时间复杂度是O（n） 这题还可以用binary search做，就是一层for loop里套一个复杂度为O（logn）的查找总时间复杂度O（nlogn）

苏小鬟 发表于 2022-08-02 17:06

楼主上来说map.find是循环一遍 已经说明了一切
懒得废话了

你这个A是N square，B是N啊。这个当然是B快。worst case，array走一半就完了。这个看不明白，把算法time complexity再多读几遍

这不是two sum吗，leetcode第一题

刚开始学习leetcode。这是leetcode的第一题。https://leetcode.com/problems/two-sum/
请问下面两个答案，你更喜欢哪一个？他俩是等价的吗？
这个map.find 不也是一个循环吗？我认为这两个答案其实是一样的。答案A可能速度更快。
请高手解答。

有人认为A是O(n^2)。 所以A不是正确答案。请赐教A到底是正确的答案，还是错误的。
A和B的complexity是不是一样的？
为什么A的实际运算速度快于B？


v = {1, 6, 3, 2, 5};
target = 11；


A）
vector<int> twoSum(vector<int>& nums, int target) {     int a=0;     int b=0;     for(int ii=0;ii<nums.size()-1;ii++)     {       for(int j=i+1;j<nums.size();j++)       {         if(nums[ii]+nums[j]==target)         {           a=ii;           b=j;         }       }     }     return {a,b};   }
 B）
  vector<int> twoSum(vector<int> &nums, int target)   {     map<int, int> m;     vector<int> v;     int n = nums.size();     for (int i = 0; i < n; i++)     {
      int diff = target - nums;       if (m.find(diff) != m.end())       {         auto p = m.find(diff);         v.push_back(p->second);         v.push_back(i);       }       m.insert(make_pair(nums, i));     }
    return v;   }

gooog 发表于 2022-08-02 16:43

我感觉得稍微学学数据结构算法
时间空间复杂度
第一个是On^2 O1
第二个是On On
你找到了为什么不直接return

刚开始学习leetcode。这是leetcode的第一题。https://leetcode.com/problems/two-sum/
请问下面两个答案，你更喜欢哪一个？他俩是等价的吗？
这个map.find 不也是一个循环吗？我认为这两个答案其实是一样的。答案A可能速度更快。
请高手解答。

有人认为A是O(n^2)。 所以A不是正确答案。请赐教A到底是正确的答案，还是错误的。
A和B的complexity是不是一样的？
为什么A的实际运算速度快于B？


v = {1, 6, 3, 2, 5};
target = 11；


A）
vector<int> twoSum(vector<int>& nums, int target) {     int a=0;     int b=0;     for(int ii=0;ii<nums.size()-1;ii++)     {       for(int j=i+1;j<nums.size();j++)       {         if(nums[ii]+nums[j]==target)         {           a=ii;           b=j;         }       }     }     return {a,b};   }
 B）
  vector<int> twoSum(vector<int> &nums, int target)   {     map<int, int> m;     vector<int> v;     int n = nums.size();     for (int i = 0; i < n; i++)     {
      int diff = target - nums;       if (m.find(diff) != m.end())       {         auto p = m.find(diff);         v.push_back(p->second);         v.push_back(i);       }       m.insert(make_pair(nums, i));     }
    return v;   }

gooog 发表于 2022-08-02 16:43

查了一下问compiler 和 IDE的人果然是LZ...
这是要和孩子一起学的节奏?

我感觉得稍微学学数据结构算法
时间空间复杂度
第一个是On^2 O1
第二个是On On
你找到了为什么不直接return


crichris 发表于 2022-08-02 18:10

第二个(B)反正是O（n） 所以return不return，都是O(n) 因为第一个循环就是ii从1到n， 这个循环里面嵌套的map.find是O(1) 所以整个是O(n)* O(1)
你为什么说第二个是On * On ?

请教一下，如何理解hash table的搜索是O（1） 谁提出的这个hash table算法，这么牛，能做到O(1)?
如果不给你c++，给你一个C，请问，你自己如何能写出一个hash table的算法？
而不是像c++里这样简单的调用一下map就算完成任务了。
c里面有indexof这个搜索，请问这个indexof的时间复杂度是多少？

LZ和隔壁贴子正好配一对，一个想教，一个想学。

LZ和隔壁贴子正好配一对，一个想教，一个想学。
cacp 发表于 2022-08-02 18:26

我问的问题，都是比较高深的。不一定他教得了。

回复 26楼gooog的帖子
hash table takes more space, this is a space/time trade off question

这个题很简单。你的思路非常好👍，我一般也是先想本笨办法，比如你的第一种方法，用target 减去你的nums compare with nums[j]. 后来你会意识到这个用时为n^2。你需要再想想更省时间的解法，第二种解法应该是优解

这个题很简单。你的思路非常好👍，我一般也是先想本笨办法，比如你的第一种方法，用target 减去你的nums compare with nums[j]. 后来你会意识到这个用时为n^2。你需要再想想更省时间的解法，第二种解法应该是优解
孤傲招财猫 发表于 2022-08-02 18:32

多谢！ 我是抄的。
我的第一个解法（A）的第二个循环，是从ii+1开始，到n结束。 也就是循环n-ii 次，并没有循环n次。为啥还是O(n)呢？
另外，第二个解法B的hash table是O（1），我还是不明白。这是怎么能做到的呢？ 还是map.insert 和map.find 不都要花费计算时间吗？
为啥hash table就会快呢？

回复 26楼gooog的帖子
hash table takes more space, this is a space/time trade off question
luyang199608 发表于 2022-08-02 18:31

我多问一句。是不是这个hash table的算法其实很复杂。一般人，是无法从零编写一个hash table？
尽管，一般人，天天把hash table挂在嘴上。

第二个(B)反正是O（n） 所以return不return，都是O(n) 因为第一个循环就是ii从1到n， 这个循环里面嵌套的map.find是O(1) 所以整个是O(n)* O(1)
你为什么说第二个是On * On ?

gooog 发表于 2022-08-02 18:22

我可能没写清楚
这两个东西不是乘起来的
分别是 时间复杂度 和 空间复杂度
该return的时候就return you will thank me later
讲道理你的知识水平和你的statement有点儿inconsistent
推荐你先学学简单的c 和数据结构和算法
直接刷题会养成很多不好的习惯...

多谢！ 我是抄的。
我的第一个解法（A）的第二个循环，是从ii+1开始，到n结束。 也就是循环n-ii 次，并没有循环n次。为啥还是O(n)呢？
另外，第二个解法B的hash table是O（1），我还是不明白。这是怎么能做到的呢？ 还是map.insert 和map.find 不都要花费计算时间吗？
为啥hash table就会快呢？
gooog 发表于 2022-08-02 18:37

for your A, 总共需要的steps：the first loop n steps, the second loop: n + n-1 + n-2 + n-3 + ... + 1 = n(n+1)/2 =n^2/2 + 2/n highest order : n^2

HashTable是以空间换时间，把所有对应的关系记住，就不用每次去计算了和遍历查询了。HashTable自己就可以设计算法，比如最简单的%，就可以。当然还牵涉其他问题，比如collision resolution，比如space/time efficiency的tradeoff引来的最佳空间利用率。这些知识数据结构课程里会讲到

多谢！ 我是抄的。
我的第一个解法（A）的第二个循环，是从ii+1开始，到n结束。 也就是循环n-ii 次，并没有循环n次。为啥还是O(n)呢？
另外，第二个解法B的hash table是O（1），我还是不明白。这是怎么能做到的呢？ 还是map.insert 和map.find 不都要花费计算时间吗？
为啥hash table就会快呢？
gooog 发表于 2022-08-02 18:37

举个简单的例子，如果你要到图书馆找一本书，书的index是一个字母一个数字 （假设字母和数字是一样多）。你第一个方法，是loop through 所有的字母，在每个字母下，loop through 所有的数字，才能找到答案。 但是如果你用 hash table, 把开头用同一个字母的所有书放在一起。知道你的书的第一个字母，就相当于你知道书架了，直接到标有那个字母的那个书架上检索数字就行了。

这个是传说中的强行转码？

我多问一句。是不是这个hash table的算法其实很复杂。一般人，是无法从零编写一个hash table？
尽管，一般人，天天把hash table挂在嘴上。
gooog 发表于 2022-08-02 18:40

刷题时候，需要补algorithm这门课的 hash table怎么工作的，会有专门的章节，而且课后作业会要求implement

lz先学费基本数据结构和算法再刷题吧，这样效率太低了

多谢！ 我们可以认为 答案A的第二个循环 complexity也不是n 吗？ for(int j=i+1;j<nums.size();j++)

gooog 发表于 2022-08-02 17:01

你要算的是n+ （n-1） + （n-2） + 直到1，结果n（n+1）/2， complexity是n^2。你把速度是减了一半，还是complexity是一样的。

for your A, 总共需要的steps：the first loop n steps, the second loop: n + n-1 + n-2 + n-3 + ... + 1 = n(n+1)/2 =n^2/2 + 2/n highest order : n^2
被逼成了怨妇 发表于 2022-08-02 19:16

怨妇说得很对。

举个简单的例子，如果你要到图书馆找一本书，书的index是一个字母一个数字 （假设字母和数字是一样多）。你第一个方法，是loop through 所有的字母，在每个字母下，loop through 所有的数字，才能找到答案。 但是如果你用 hash table, 把开头用同一个字母的所有书放在一起。知道你的书的第一个字母，就相当于你知道书架了，直接到标有那个字母的那个书架上检索数字就行了。


被逼成了怨妇 发表于 2022-08-02 19:38

多谢！明白了。 我有个问题。
假设两个图书馆A和B。A是hash table。每次管理员都把同字母的还书放在一起。方便读者查阅。
B不是hash table。每次管理员就随便把书扔到书架上。读者每次查阅很费时。但是管理员却很轻松。
问题：读者查阅的时间加上管理员送书上架的时间，对于A和B，是不是一样的？

建议楼主先学一下基本知识再刷题。别一开口就是map是哈希表这样的笑话，很伤人品的，好伐。

果然华人绝大部分都不懂C++，也不知道前几天讨论C++用什么工具居然能讨论到20多页。。。 看遍5页， 也没人能告诉Lz。。。
map是 red-black tree， 不是hash map。 请用unordered_map

仔细一看你用的不是hashmap是map 那复杂度就上升了，因为map.find好像是log（n）

多谢！明白了。 我有个问题。
假设两个图书馆A和B。A是hash table。每次管理员都把同字母的还书放在一起。方便读者查阅。
B不是hash table。每次管理员就随便把书扔到书架上。读者每次查阅很费时。但是管理员却很轻松。
问题：读者查阅的时间加上管理员送书上架的时间，对于A和B，是不是一样的？


gooog 发表于 2022-08-02 19:59

其实你这个思路是对的，如果只查找一次那确实两个算法没啥区别。实际工作中一般是写一次读多次，那hashmap的优势就体现了。

twosum 那里指针换来换去的还是容易搅乱一些人的。
有的人比较变态追求代码简短，那3，5行就写完了。

多谢！明白了。 我有个问题。
假设两个图书馆A和B。A是hash table。每次管理员都把同字母的还书放在一起。方便读者查阅。
B不是hash table。每次管理员就随便把书扔到书架上。读者每次查阅很费时。但是管理员却很轻松。
问题：读者查阅的时间加上管理员送书上架的时间，对于A和B，是不是一样的？


gooog 发表于 2022-08-02 19:59

我的理解： 一般设计到速度，考虑的都是大量数据，不仅仅是两个图书馆26个字母而已。就想想你有millions letters millions numbers 需要查找，还有millions users。 “管理员把书整理到书架上”，在hash table 就是通过一个方程实现而已，相对于检索而言，花的时间可以忽略不计。

刷题，解题不是目的 你要通过做题来巩固自己对算法和数据结构的理解 这道题就是two sum啊，有无数道的变种的，你不需要系统地学习hashmap, list, stack, heap之类的数据结构，你也可以理解怎么做的，但是，这不是刷题的意义所在。 举个例子，我要是面试官，面你这样的题，你觉得你写完了我就能给你offer吗？那你想的大包裹也太好拿了，凭啥这就给你几十万的package呢？ 讲讲hashmap？在底层是怎么实现的呢？hash大概有哪些算法呢，hash collision讲一讲？有哪些解决办法呢？atomic的时间复杂度为什么是你说的那样的呢？ 或者再扩充一些，在系统设计里面，有consistent hash的概念，能简单讲讲吗....？
真的不是你刷个two sum就能拿到offer的

回复 49楼爱码仕的帖子
跟她说这么多，我看她讲的都无语了

刚开始学习leetcode。这是leetcode的第一题。https://leetcode.com/problems/two-sum/
请问下面两个答案，你更喜欢哪一个？他俩是等价的吗？
这个map.find 不也是一个循环吗？我认为这两个答案其实是一样的。答案A可能速度更快。
请高手解答。

有人认为A是O(n^2)。 所以A不是正确答案。请赐教A到底是正确的答案，还是错误的。
A和B的complexity是不是一样的？
为什么A的实际运算速度快于B？


v = {1, 6, 3, 2, 5};
target = 11；


A）
vector<int> twoSum(vector<int>& nums, int target) {     int a=0;     int b=0;     for(int ii=0;ii<nums.size()-1;ii++)     {       for(int j=i+1;j<nums.size();j++)       {         if(nums[ii]+nums[j]==target)         {           a=ii;           b=j;         }       }     }     return {a,b};   }
 B）
  vector<int> twoSum(vector<int> &nums, int target)   {     map<int, int> m;     vector<int> v;     int n = nums.size();     for (int i = 0; i < n; i++)     {
      int diff = target - nums;       if (m.find(diff) != m.end())       {         auto p = m.find(diff);         v.push_back(p->second);         v.push_back(i);       }       m.insert(make_pair(nums, i));     }
    return v;   }

gooog 发表于 2022-08-02 16:43

楼主努力学习的精神可嘉

这题经典的用hash table查就是O(N) 复杂度，你要傻傻的2重循环就是N^2， 建议补一下基础吧