发嗲鞋子

文章
3
资源
0
加入时间
2年10月21天

ARTS挑战第六周AlgorithmReviewTipsShare

Algorithm560. 和为K的子数组 使用前缀和数组,在枚举所有子数组时需要优化,否则N^2复杂度会超时。因为符合条件的结果是sum[j]-sum[i] == k,其中j>i。因此在遍历到sum[j]时,其实只需要知道有多少个i使得sum[i] = sum[j]-k,从而将结果加上这个数。这里需要注意的地方是,我们需要知道i<j的情况,而不包含i == j的情况,因此先根据前面统计的前缀和数组中,sum[i]出现的个数更新ans,再将sum_j的值更新ma