网易首页 > 网易号 > 正文 申请入驻

2026-10-31:数对的最大强度。用go语言,给定一个整数数组 nums。需要从数组中选出两个位置不同的元素,组成一个数对。该数对的强度等于

0
分享至

2026-10-31:数对的最大强度。用go语言,给定一个整数数组 nums。需要从数组中选出两个位置不同的元素,组成一个数对。该数对的强度等于:这两个元素的乘积,除以它们的最大公约数的平方。请计算并返回所有可能数对中能够得到的最大强度值。

2 <= nums.length <= 2000。

1 <= nums[i] <= 100000。

输入: nums = [2,3,5]。

输出: 15。

解释:

选择 i = 1 和 j = 2,得到强度:

(3 * 5) / gcd(3, 5)2 = 15 / 1 = 15,这是所有数对中的最大值。

题目来自力扣4010。

大体步骤如下: 一、先看清"强度"这个式子的数学本质

数对 (x, y) 的强度定义为:

设 ,那么可以写成 ,且 。代入后:

结论:强度 = 两个数各自"约掉公因子之后"的乘积。所以要让它大,需要两个条件同时满足:

  1. 1. 两个数本身尽量大(乘积的分子大);

  2. 2. 它们的最大公约数尽量小(除以的 小)。

顺带一个副产品: 一定能被 整除,所以代码里做整数除法 不会有任何取整误差,结果是精确的。这一点后面判断剪枝安全性时会用到。

题目数据范围 ,两两数对一共约 对,所以"全部枚举"本身是可行的baseline;这份代码的价值在于用一个上界剪枝把绝大多数情况压到远低于这个数。

二、整体策略:排序 + 构造一个"只依赖乘积"的上界

暴力枚举的问题是每一对都要算一次 。代码的思路是:

能不能在不算 的前提下,先判断"这一对绝对不可能刷新最优解"?如果能,就直接跳过不做 。

要做到这件事,需要两样东西:

  • •一个便宜的上界:只靠 就能算出"这对的强度最多是多少";

  • •一个单调的枚举顺序:保证一旦上界跌破当前最优,后面所有候选只会更差,可以直接break,而不是继续遍历。

排序负责第二件事,全局 负责第一件事。

三、步骤 1:降序排序(为单调性铺路)

代码用slices.SortFunc配合比较函数b - a,把nums排成从大到小。

排序不是为了"找最大的两个数"这么简单(最大的两个数不一定是最优解,例如[15, 10, 6]中15×10的强度只有 6,而10×6的强度是 15)。排序的真正目的是让后面双重循环的枚举顺序具备单调性:

  • • 外层i递增时, 的值递减;

  • • 内层遍历nums[:i],即下标 ,因为数组已降序, 的值也是递减的,而且恒有 。

于是对固定的 ,内层循环中乘积 随着 从nums[0]走到nums[i-1]是严格单调不增的。这个性质是break能够成立的前提。

补充一句副作用:这是原地排序,会直接打乱调用方传入的 slice 顺序;如果调用方还依赖原顺序,需要先拷贝一份。

四、步骤 2:求"全局 gcd",构造合法上界

代码接着从头到尾把所有元素卷进一个gcd,得到allGcd,即整个数组所有元素的公共最大公约数,再平方得到allGcd2。

初始值是 0,而 (gcd函数里a = 0时循环一次都不进,直接返回b),所以第一次滚动等价于"把allGcd初始化成第一个元素",这是标准的写法。由于 满足交换律和结合律,遍历顺序不影响结果。

关键的不等式推导:

  1. 1.allGcd整除数组里的每一个元素,所以它也整除 ,也整除 ;

  2. 2. 既然allGcd同时整除 和 ,那它必然整除 ;

  3. 3. 因此 ,进而 ;

  4. 4. 分子相同、分母更大 商更小,于是:


右边就是那个"便宜的上界"——它完全不需要知道这一对具体的 ,只要一次乘法一次除法就能算出来。而且它是"任意数对通用的",对数组里所有数对同时成立。

还有个细节值得一提: 未必能被 整除(因为allGcd只是 的下界,不一定等于 ),所以mul / allGcd2是向下取整的整数除法。向下取整只会让这个上界更小(更紧),而不会让它失效—— 真实强度 依然成立吗?这里要小心方向:真实强度 (实数除法),而真实强度是整数,所以真实强度 。是的,因为一个整数若不超过实数 ,那它也不超过 。所以取整后的上界依然是合法上界,剪枝安全。

五、步骤 3:双重循环 + 上界剪枝

外层枚举 (从 0 到 ), ;内层枚举 , 。这样每个无序数对恰好被访问一次,不重不漏。

内层每一步做三件事:

  1. 1. 先算mul = x * y(一次乘法,极便宜);

  2. 2. 算上界mul / allGcd2,与当前最优ans比较:

  • • 如果上界 ≤ ans:说明这对的真实强度 上界 ans,绝对不可能刷新最优;而且因为 继续往下走时mul只会更小、上界只会更低,后面所有 也都不可能刷新最优—— 于是直接break,连 都不用算。

  • • 如果上界 > ans:说明这对"还有希望",这时才付出代价真正去算 ,再用 更新ans。

3.ans初始为 0,而题目保证元素 ,所以第一对的上界一定 ,不会一开始就误剪。

这个break的正确性完全建立在第四节的继承和第三节的单调性之上,缺一不可:

  • • 没有单调的枚举顺序(比如乱序),即使某一对的上界不达标,也不能推断后面的对不达标,就只能continue而非break,剪枝收益大打折扣;

  • • 没有合法上界,break就可能把真正的答案剪掉。

六、用nums = [2, 3, 5]完整走一遍
  1. 1.降序排序→[5, 3, 2]。

  2. 2.求全局 gcd: , , ,所以allGcd = 1,allGcd2 = 1。上界退化成"就是乘积本身"。

  3. 3.外层 i = 0:nums[:0]为空,内层不执行。

  4. 4.外层 i = 1, :

  • • 内层 :mul = 15,上界ans = 0,有希望 → 算 → 强度 →ans = 15。

5.外层 i = 2, :

  • • 内层第一个 :mul = 10,上界ans = 15→ 立刻break,剩下的 直接跳过。

6. 返回 15。

验证一下被跳过的两对: 强度 10、 强度 6,确实都小于 15,剪枝没有剪错。

七、这个剪枝到底有多强?(以及什么时候会失效)

有意思的是,这个剪枝存在一个"两难"结构,让它在绝大多数输入下都异常高效:

  • • 如果数对的 普遍很小→ 强度值很大→ans迅速涨到一个很大的数 → 上界很容易就撞上ans→ 剪枝极早触发;

  • • 如果数对的 普遍很大→ 说明元素之间共享大量因子 → 全局allGcd也倾向于变大 → 上界 被压得很低 → 上界本身就不容易超过ans→ 剪枝同样很早触发。

两个极端都利于剪枝,所以实践中内层循环往往每个 只跑一两次就break。

但它并非没有最坏情况:漏洞在于"全局 gcd 小、局部两两 gcd 大"的输入。典型构造是取一批大质数 ,令数组元素是这些质数的两两乘积 。任意两个元素共享一个质因子(局部 gcd ≈ 300),但任意三个元素的公共 gcd = 1(全局allGcd = 1)。此时:

  • • 上界 ,非常松;

  • • 而真实强度只有约 ,ans很小;

  • • 于是上界几乎永远大于ans,剪枝几乎完全失效,内层会跑满,退化成 次完整枚举。

即便如此, 时也就约 次 ,完全在限制内,所以这个上界分析上是 、实践上远好于 ,属于"稳赚不赔"的优化。

八、复杂度分析

记 数组长度( ), ( )。

时间复杂度

  • • 降序排序: (原地 pdqsort,比较函数 );

  • • 求全局 gcd: 次欧几里得,单次 ,合计 ;

  • • 双重循环:迭代次数上界。每次迭代是 的乘法+比较,只有未触发剪枝的那些迭代才额外付一次 的 。因此最坏 ,剪枝生效时显著低于此。

总时间复杂度: ,由双重循环主导,即 。

由于 ,欧几里得的迭代轮数最多十几轮且常数极小,工程上可以直接视作 ;代入 即约 次基本运算,毫秒级。

额外空间复杂度

  • • 排序是原地的,不分配新数组;nums[:i]只是复用的切片头(三个机器字),循环中不产生堆分配;

  • • 排序递归栈 ;

  • •ans、allGcd、mul等均为 的标量。

总额外空间复杂度: ,全来自排序的递归栈;忽略栈则可视为 。

九、两个实现层面的小提醒

  1. 1.整数宽度:mul = x * y最大可达 ,已超出 32 位int。在 64 位平台上 Go 的int是 64 位,没问题;若在 32 位平台编译则会溢出,稳妥做法是把中间变量换成int64(函数返回值已经是int64,说明作者也考虑到了量级)。

  2. 2.原地修改:如第三节所述,排序会打乱传入的 slice,这是函数的可观察副作用。

Go完整代码如下:

package main

import (
"fmt"
"slices"
)

func maxPairStrength(nums []int)int64 {
slices.SortFunc(nums, func(a, b int)int { return b - a })

allGcd := 0
for _, x := range nums {
allGcd = gcd(allGcd, x)
}
allGcd2 := allGcd * allGcd

ans := 0
for i, x := range nums {
for _, y := range nums[:i] {
mul := x * y
if mul/allGcd2 <= ans {
break
}
g := gcd(x, y)
ans = max(ans, mul/(g*g))
}
}
returnint64(ans)
}

func gcd(a, b int)int {
for a != 0 {
a, b = b%a, a
}
return b
}

func main() {
nums := []int{2, 3, 5}
result := maxPairStrength(nums)
fmt.Println(result)
}

Python完整代码如下:

# -*-coding:utf-8-*-

from math import gcd

def max_pair_strength(nums):
# 按从大到小排序
nums.sort(reverse=True)

# 计算所有元素的整体 gcd
all_gcd = 0
for x in nums:
all_gcd = gcd(all_gcd, x)

all_gcd2 = all_gcd * all_gcd

ans = 0
for i, x in enumerate(nums):
for y in nums[:i]:
mul = x * y

if mul // all_gcd2 <= ans:
break

g = gcd(x, y)
ans = max(ans, mul // (g * g))

return ans

def main():
nums = [2, 3, 5]
result = max_pair_strength(nums)
print(result)

if __name__ == "__main__":
main()

C++完整代码如下:

  

using namespace std;

int gcd_int(int a, int b) {
while (a != 0) {
int t = b % a;
b = a;
a = t;
}
return b;
}

long long maxPairStrength(vector nums) {
sort(nums.begin(), nums.end(), greater());

int allGcd = 0;
for (int x : nums) {
allGcd = gcd_int(allGcd, x);
}
long long allGcd2 = 1LL * allGcd * allGcd;

long long ans = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
int x = nums[i];
for (int j = 0; j < i; ++j) {
int y = nums[j];
long long mul = 1LL * x * y;

if (mul / allGcd2 <= ans) {
break;
}

int g = gcd_int(x, y);
ans = max(ans, mul / (1LL * g * g));
}
}
return ans;
}

int main() {
vector nums = {2, 3, 5};
long long result = maxPairStrength(nums);
cout << result << endl;
return0;
}

我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
别再把自己裹成球了!科学家发现:这种“微冷”状态,正在悄悄延长你的寿命

别再把自己裹成球了!科学家发现:这种“微冷”状态,正在悄悄延长你的寿命

爱医斯坦
2026-11-18 11:06:04
八国联军侵华,7个国家瓜分中国,唯独一国反对,如今成超级大国

八国联军侵华,7个国家瓜分中国,唯独一国反对,如今成超级大国

文史达观
2025-03-08 06:45:05
中国股市:写给处于严重亏损的股民们的一封信,此文,很短很深

中国股市:写给处于严重亏损的股民们的一封信,此文,很短很深

屿探涨
2026-11-17 11:25:04
APEC合影现场!普京与特朗普再度握手

APEC合影现场!普京与特朗普再度握手

看看新闻Knews
2026-11-19 12:35:07
东南亚手机市场雪崩,OPPO跌62%,仅苹果增长

东南亚手机市场雪崩,OPPO跌62%,仅苹果增长

上峰视点
2026-11-17 09:09:58
一旦恢复该规定,中国结婚率或将大幅上涨,离婚率也会有所下降

一旦恢复该规定,中国结婚率或将大幅上涨,离婚率也会有所下降

福建睿平
2026-10-28 07:23:25
拒绝奥地利足协!德籍华裔球员想来中国踢球,明年能否加盟国安?

拒绝奥地利足协!德籍华裔球员想来中国踢球,明年能否加盟国安?

体坛鉴春秋
2026-11-19 19:24:07
广东一对夫妻买“霸王茶姬”中49999元心愿大奖,全国仅9份,当事人:准备给老婆买金手镯,或一起去旅游

广东一对夫妻买“霸王茶姬”中49999元心愿大奖,全国仅9份,当事人:准备给老婆买金手镯,或一起去旅游

扬子晚报
2026-11-19 21:43:12
直击:马斯克乘车离开酒店或前往APEC系列活动现场

直击:马斯克乘车离开酒店或前往APEC系列活动现场

界面新闻
2026-11-19 11:07:25
中美俄发布和平宣言,一致反对国际刑事法院滥用管辖权,杜特尔特迎来新希望

中美俄发布和平宣言,一致反对国际刑事法院滥用管辖权,杜特尔特迎来新希望

光电科技君
2026-11-19 22:07:05
黄仁勋输得不冤!董事会的十位大佬,一群金融营销精英,到底是怎么上桌的?

黄仁勋输得不冤!董事会的十位大佬,一群金融营销精英,到底是怎么上桌的?

起点人文
2026-11-19 18:49:04
APEC会议场馆成热门打卡点,深圳市民心愿甜蜜又实在:把车厘子价格“打”下来

APEC会议场馆成热门打卡点,深圳市民心愿甜蜜又实在:把车厘子价格“打”下来

极目新闻
2026-11-19 21:23:40
离称霸,字节只差一个聊天软件了!

离称霸,字节只差一个聊天软件了!

城事堂
2026-11-17 14:09:44
太可惜!亚运村这家8年老店关了!

太可惜!亚运村这家8年老店关了!

亚奥在线
2026-11-19 16:08:37
特朗普下榻酒店最低房价800,这波操作我看傻了

特朗普下榻酒店最低房价800,这波操作我看傻了

风起见你
2026-11-19 23:18:08
小心!欧洲被打服了,中东也不闹了,美国的目标只剩下东亚

小心!欧洲被打服了,中东也不闹了,美国的目标只剩下东亚

西府赵王爷
2025-03-22 15:47:18
男子在二手平台挂出一块劳力士,很快有人出价19万5,可交易当天来的是个14岁女孩,男子感觉不对劲立刻报警

男子在二手平台挂出一块劳力士,很快有人出价19万5,可交易当天来的是个14岁女孩,男子感觉不对劲立刻报警

环球网资讯
2026-11-19 10:01:08
果然!中国男篮筛掉5人,赵睿崔永熙离队,赵继伟队长,周琦压阵

果然!中国男篮筛掉5人,赵睿崔永熙离队,赵继伟队长,周琦压阵

萌兰聊个球
2026-11-19 22:16:18
俄罗斯可能要对法国下手了!因为俄罗斯确认了一件事,那就是如今的法国,成为了冲突的参与方!

俄罗斯可能要对法国下手了!因为俄罗斯确认了一件事,那就是如今的法国,成为了冲突的参与方!

扶苏聊历史
2026-11-19 18:17:35
塔图姆把球扔向裁判吃T,凯尔特人最后一攻没了

塔图姆把球扔向裁判吃T,凯尔特人最后一攻没了

晚风知我意21
2026-11-19 23:39:37
2026-11-19 23:59:00
moonfdd incentive-icons
moonfdd
福大大架构师每日一题
1584文章数 83关注度
往期回顾 全部

科技要闻

老黄想回来?英伟达董事会:没门

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

体育要闻

伪强队?拥4亿豪阵欧国联6连败+世界杯出局

娱乐要闻

陈晓楠对话厉娜和许飞引全网热议

财经要闻

10万人逼宫英伟达,黄仁勋要复职了?

汽车要闻

全新红旗H9最有意思的地方,是它开始有自己的豪华逻辑了

态度原创

本地
手机
亲子
公开课
军事航空

本地新闻

乌兰察布:以前种土豆,现在种Token

手机要闻

2026年最后一款超模旗舰!小米18标准版屏幕、性能、影像全面领跑

亲子要闻

宝宝气人但是聪明的4个行为

公开课

李玫瑾:为什么性格比能力更重要?

军事要闻

美军在中东再成三航母之势

无障碍浏览 进入关怀版