Amazon电面, 跪穿

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ykwwind 发表于 2016-5-13 11:23
不是求和，是求那个sub array.....

如果求subarray 记一下最大值时的index就行。

1. public int[] maxProductLength3(int[] nums)
   
2. {
   
3.     if (nums.length < 3)
   
4.         return null;
   
5.     int current = 1;
   
6.     int resultIndex = -1;
   
7.     int result = Integer.MIN_VALUE;
   
8.     for (int i = 0; i < nums.length; i++)
   
9.     {
   
10.         current *= nums[i];
    
11.         if (i > 2)
    
12.         {
    
13.             current /= nums[i-3];
    
14.         }
    
15.         if (i >= 2 && current >= result) {result = current; resultIndex = i;}
    
16.     }
    
17.     return new int[] {resultIndex-2, resultIndex-1, resultIndex};
    
18. }
    
19. 
    

复制代码

只找三个最大的好像不用sort，直接扫一遍就可以了。。

Mark6 发表于 2016-5-13 23:36
只找三个最大的好像不用sort，直接扫一遍就可以了。。

为什么啊？

碰到烙印还是 祈祷吧

vae371 发表于 2016-5-31 07:57
为什么啊？

用三个变量保存当前最大的三个值？

用一个窗口保存当前三个值，然后去一个加一个扫一遍就好了

想了个O(n)解法，大家看看对不：

1. 扫一遍array, 记录最大的三个值a, b, c和最小的两个值c, d。
2. return max(a*b*c, a*c*d)

这样顺序也保留了

补充内容 (2016-5-31 10:42):
记录两个最小值是为了处理有两个负数相乘得出了很大的正数的情况。

烙印。。。不说了呵呵