1.自然考虑双重循环,复杂度O(n2)不允许。
2.发现一个关键性质:ai的和小于等于1e5 , 那么对ai 去重之后不同数的个数最多为1e5个。 发现这个性质以后,可以直接对去重后的集合双重循环暴力。显然复杂度O(值域) ,可过本题。
Python代码
你获得了一组正整数碎片,每个碎片上写有一个数字。你好奇每一个碎片上的数字能否表示为另外两块碎片上的数字之和(允许同一块碎片被选取两次,即 j 和 k 可以相等)。
给定一个长度为 n 的正整数序列 a1,a2,…,an,对于每个 i,请判断是否存在下标 j 与 k(1≤j,k≤n,允许 j=k)使得 ai=aj+ak。
约束条件:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册