LintCode 1844 · subarray sum equals to k II | 子数组和为K II

题目

1844 · 子数组和为K II

暴力算法 O(n^3)

把所有子数组都撸一遍。

伪代码：

for 子数组左端点 start //O(n)
    for 子数组右端点 end  //O(n)
        for start 到 end 求和  //O(n)
            判断是不是k

暴力算法优化 O(n^2)

用前缀和数组在 O(1) 时间内直接算得子数组和

伪代码：

for 子数组左端点 start //O(n)
    for 子数组右端点 end  //O(n)
        判断prefixSum[end + 1] - prefixSum[start]  //O(1)
            是不是k

for右端点end

用 HashSet / set
对于一个 end，要使得 start-end 之间最短，start 就要尽可能大

• 如何找到 prefixSum[start] = prefixSum[end + 1] - k 的最大 start?
  用 HashMap / dict 记录得到某个 prefixSum 的最大 start 是多少