在数组中找到两个元素，总和为k [duplicate]

  可能重复：   给定两个数组a和b。找出所有元素对（a1，b1），使得a1属于数组A，b1属于数组B，其总和a1 + b1 = k。 给定：未排序的数组
A
整数 输入：整数
k
 输出：所有两个元素集合，每个元素的总和等于O（n）中的
k
。 例： 
A = {3,4,5,1,4,2}
 输入：6 输出：
{3,3}, {5,1}, {4,2}
 注意：我知道一个O（n logn）解决方案，但这需要对数组进行排序。有没有办法在O（n）中解决这个问题。可以使用非平凡的C ++数据结构，即空间没有限制     
2019-11-05 6 条评论
分享

没有找到相关结果

    已邀请:

    郡晒景沧

    创建一个恒定时间查找表（哈希），以便查看数组中是否包含特定的整数（O（n））。然后，对于数组中的每个元素，查看是否包含
    k-A[i]
    。这需要每个元素保持恒定的时间，因此总共有O（n）时间。这假设元素是不同的;使重复元素工作并不困难。     
    2019-11-05 0 0
    分享

    河饶办斜施

    我只是一个简单的算法： 创建一个位域，表示从0到k的数字，标记为B. 对于A中的每个数字i 设置B [i] 如果设置了B [k-i]，则将（i，k-i）添加到输出 现在正如人们提出的那样，如果你需要输出数字3的两个实例来输出（3,3），那么你只需要切换上述算法中最后两个语句的顺序。 此外，我确信这个算法有一个名称，或者至少有一个更好的名称，所以如果有人知道我会赞赏一个评论。     
    2019-11-05 0 0
    分享

    镰茧钩

    http://codepad.org/QR9ptUwR 这将打印所有对。该算法与@bdares上面讲述的相同。 我使用过stl贴图，因为我们在STL中没有哈希表。     
    2019-11-05 0 0
    分享

    窃誓额

    一个可以减少， 元素唯一性位， 对此。没有O（n）。     
    2019-11-05 0 0
    分享

    拈吉勉犬姆

    有k对整数总和为k：{0，k}，{1，k-1}，...等。创建一个大小为k + 1的数组B，其中元素是布尔值。对于阵列A的每个元素e，如果e＆lt; = k＆amp;＆amp; B [e] == false，设置B [e] = true，如果B [k-e] == true，则发出对{e，k-e}。对于负整数，需要略微延长。     
    2019-11-05 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.038341999053955