狗昂赛

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

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

补充内容 (2019-5-19 04:38):
第一题的i被系统自动过滤了？A[ i ] == A[ j ]

第一题，用map存下某个value最小的sum，O(n)搞定。

1. 
   
2.     static int getMaxSum(int[] data) {
   
3.         int sum = 0;
   
4.         int ans = Integer.MIN_VALUE;
   
5.         Map<Integer/*value*/, Integer/*pre sum*/> valueMap = new HashMap<>();
   
6.         for (int value : data) {
   
7.             sum += value;
   
8.             if (valueMap.containsKey(value)) {
   
9.                 int preSum = valueMap.get(value);
   
10.                 ans = Math.max(ans, sum - preSum);
    
11.                 valueMap.put(value, Math.min(preSum, sum - value));
    
12.             }
    
13.             else {
    
14.                 valueMap.put(value, sum - value);
    
15.             }
    
16.         }
    
17.         return ans;
    
18.     }
    

复制代码

第一道题使得A == A[j]是什么意思啊

yyoung 发表于 2019-5-19 02:56
第一道题使得A == A[j]是什么意思啊

A[i] == A[j]

yyoung 发表于 2019-5-19 02:56
第一道题使得A == A[j]是什么意思啊

1. A[i] == A[j]

复制代码

第一题楼主怎么解啊？

raincode 发表于 2019-5-18 16:27
第一题楼主怎么解啊？

第一题感觉用map + presum 可以O(N)?

iiimisery 发表于 2019-5-19 06:10
第一题感觉用map + presum 可以O(N)?

用map的话如果所有元素都一样，时间复杂度是O (N^2)？

yyoung 发表于 2019-5-18 17:19
用map的话如果所有元素都一样，时间复杂度是O (N^2)？

map的key是元素, value是这个元素最小的presum

楼主给力，第三题能否稍微解释一下思路？

也想要知道 第一题有没有甚么好的思路