Beginner
Wins0n
全部博文(12)
2014年(12)
分类: IT职场
2014-07-18 15:41:30
因为是递增数组,所以第一次求出a[low]+a[high]==k,则是乘积最小的那个。 当两个数x+y=k,当x和y越接近乘机越大。证明如下:
x+y=k
两边平方:
(x+y)^2=k^2
然后继续变:
(x-y)^2+4xy=k^2
很显然x和y越接近,xy就越大。故让x和y尽量相差很大。 从两边往中间扫描即可,O(N)时间
上一篇:移位运算注意
下一篇:没有了
登录 注册