FB 高频题目A maximum sized Subsequence, sum is a given number

原帖地址:米群网

看到很多人被面到这个题目了,大意是求某个连续子数组, 这个子数组的和是某个数,而且这个子数组的length还必须是最大的那个。

个人感觉是维护一个HashMap , prefixSum 表示区间(0 , index]的前缀和。 如果有多个index 它们的prefixSum 相等,那么保持最左边的那个。 那么subSequence Sum 假设是 [i+1, j] 那么其实就是 prefixSum[ j ]- prefixSum 【i】 == target. 其实也就是inspect if prefixSum[j] – target is in the hashMap, if yes, get index of prefix[j] – target which is i, then the length is j – i. 在循环的时候也要维护HashMap, 为了保证prefixSum 的 index 是最左面的,所以只在map 没有prefixSum的情况下更新。 还要注意一个特例,那就是prefixSum 不包含任何元素的情况, 其实index 是-1,

public int maxSizedSubSequence(int [] num, int target){
Map map = new HashMap();
map.put(0, -1);
int sum = 0;
int maxLength = 0;
for(int i = 0 ;i < num.length; ++i){ sum += num【i】; if(!map.containsKey(sum)){ map.put(sum, i); } if(map.containsKey(sum – target)){ int prevIdx = map.get(sum – target); maxLength = Math.max(maxLength, i – prevIdx); } } return maxLength; } )