arrays - 给定 4 个数组，未排序，找到所有可能的四元组，其总和

转载 作者：塔克拉玛干 更新时间：2023-11-03 04:38:10 24 4

给定四个未排序的等长数组，它们中有唯一的元素，但跨数组的元素可能会发生冲突，因此我们被要求从每个数组中选择一个元素并满足此条件“x1+x2+x3+x4 < m"并计算所有可能的解决方案。

我们能否做一些比对所有数组排序并在 O(n^3*logn) 中完成更好的事情？

最佳答案

1. 生成一个数组，其中包含 x1 和 x2 中元素之间的所有总和。这将有 O(n^2) 个元素。让我们称它为 arr0
2. 对 x3 和 x4 做同样的事情。让我们称它为 arr1
3. 对两者进行排序

4. 现在我们已将问题简化为查找 2 个排序数组中元素之间的总和 < m 的数量。

   p0 = 0
   p1 = arr1.length - 1
   qty = 0
   while(p0 != p1)
       while(p1 >= 0 and arr0[p0] + arr1[p1] >= m) p1--;
       if (p1 <= p0) break;
       qty += p1
       po++
   

这个小算法将在 O(length(arr0) + length(arr1)) 中解决这个问题，因为 p1 指针总是减少，p0 总是增加，对于每个循环，我们总是增加或减少其中之一

总的来说，这给了我们一个 O(n^2) 来生成对，O(n^2 * log n^2) 来对它们进行排序，O(n^2) 来计算四元组。

关于arrays - 给定 4 个数组，未排序，找到所有可能的四元组，其总和 <m，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52008872/

24 4 0

• MySQL 总和 + 总和

  我基本上有三个表: hunt_c_usershunt_c_collected_eggshunt_c_achievements 我目前只使用 hunt_c_users 和 hunt_c_collecte

• SQL 总和

  我已经计算了不同表中计数的总和。这会执行两次，每个 performanceID 一次。现在我想得到两个总和的总和。 下面是我目前做的两个总和的代码: SELECT SUM((COUNT (Bo

• Jquery 总和

  我有一个对 2 个值求和的脚本。我计划添加更多值(value)，但首先我需要让它发挥作用。人们告诉我给他们 NUMBER 值，所以我这样做了，但现在它甚至没有给出输出。 base = 0; $("#F

• MongoDB - 总和

  我正在尝试计算在我们的数据库中跟踪的花费总额。每个订单文档包含一个字段“total_price” 我正在尝试使用以下代码: db.orders.aggregate({ $group: {

• 基于在另一个表中查找代码和值的 Excel 总和

  给定 Excel 2013(或更高版本)中的 2 个命名表: tbl发票 ID InvRef Total 1 I/123 45 2 I/234

• 特殊表格之间的 VBA 总和

  希望你们一切都好。我来这里是因为我从今天早上开始就试图解决一个问题，我再也受不了了。 这就是上下文:我有一个 excel 工作簿，其中有不同的工作表，其中包含不同国家/地区的不同商业计划。我的目标是制

• sql - 在查询结果中插入行(总和)

  我有一份报告显示客户订购的产品及其价格: CompanyA Product 7 14.99 CompanyA Product 3 45.95 CompanyA Prod

• python - Redis时间序列-总和

  我使用此python客户端: https://github.com/ryananguiano/python-redis-timeseries 如何汇总所有匹配？ ts = TimeSeries(cli

• excel - 总和/计数公式自动调整插入的行

  希望创建一个总和和计数公式，该公式将自动调整以适应范围内插入的新行。 例如，如果我在单元格 D55 中有公式 =SUM(D17:D54)。每次我在该范围内插入新行时，我都需要更改公式的顶部范围来解释它

• python - 聚合具有相同日期的列(总和)

  所以，我需要聚合日期相同的行。 到目前为止，我的代码返回以下内容: date value source 0 2018-04-08 15:52:26.1

• javascript - 将表中的数值相加(总和)

  我有数字输入 数量约为 30 我需要将它们全部汇总到一个字段 我拥有的在下面 查看:

• 具有特定数量条目的列的 MYSQL 总和

  您好，我正在尝试根据以下数据计算过去三个月中出现不止一次的不同帐户 ID 的数量；我想要 2 作为查询结果，因为 test1@gmail.com 和 test2@gmail.com 出现超过 1 次。

• php - 如何从一个表中选择与另一表中的差异(总和)？

  我有两个带有以下字段的表: ... orders.orderID orders.orderValue 和 payments.orderID payments.payVal 在 payments.pay

• 来自别名未知列的 MySQL 总和

  我想按 image_gallery 和 video_gallery 两列的 DESC 进行排序。 SELECT b.*, c.title as category, (S

• mysql - 如何从别名查找mysql中的总计(总和)？

  实际上我的原始数据库为 SELECT sum(data1,data2) as database_value,sum(data3,data4) as database_not_value from t

• javascript - JavaScript 总和

  我试图获取三个分数中每一个的值并将它们相加并显示在“总计:”中。我的问题是，我不知道如何做到这一点，以便每次其中一个分数值发生变化时，相应的总分值也会随之变化。 我可以在某处调用“onchange”来

• 按第一个分组的元组列表中元组的第二个和第三个元素的 Python 总和

  如何获得按第一个值分组的元组列表中第二个和第三个值的总和？ 即: list_of_tuples = [(1, 3, 1), (1, 2, 4), (2, 1, 0), (2, 2, 0)] expec

• python - 总和、平均和其他

  我正在尝试将我的列表中的整数转换为列表的总和和平均值，并说明任何低于冰点 F<32 的温度。每当我尝试获取总和或平均值时，我都会收到错误提示“+: 'int' 和 'str' 不支持的操作数类型”。我

• ios - NSDecimalNumber 总和

  在我的 ios 项目中，我使用了两个实体 (CoreData):具有一对多关系的 Person 和 Gifts 我知道如何计算给一个人的礼物总和: NSDecimalNumber *orderSum=

• SQLITE:显示每个类别的总计(总和)

  我有两个表(输入和类别): CREATE TABLE categories ( iId INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT, sNam