560. 和为 K 的子数组

560. 和为 K 的子数组 - 力扣（LeetCode）

class Solution {
public:
  int subarraySum(vector<int>& nums, int k) {
    int Size = nums.size();
    int Count = 0;
    int *Copy = new int[Size];
    for (int i = 0; i < Size; ++i)
      Copy[i] = nums[i];

    for (int L = 0; L < Size; ++L) {
      int Sum = 0;
      for (int R = L; R >= 0; --R) {
        Sum += Copy[R];
        if (Sum == k)
          ++Count;
      }
    }

    delete[] Copy;
    return Count;
  }
};

竟然卡常！$\mathrm O\left(n^2\right)$ 方法只能拷贝成 C-like 数组然后再跑，否则过不了。

这里千万要记得一点：像这种「最大子串 XX」问题，首先要考虑的是以 i 为结尾的子串，在确定这个 i 之后，从后向前考察数组，也就是

$$ [i, i]\to[i - 1, i]\to\cdots\to[j, i]\to[j-1,i]\to\cdots\to[0, i] $$

所以两层循环：一层从 0 开始正着的，一层从 i 开始反着的。

前缀和 + 哈希优化方法其实也非常直观和容易理解。关键就在于利用前缀和的性质逐步推出关系式：

$$ \begin{align} &\text{Prefix}[i]=\text{Prefix}[i-1]+\text{nums}[i]\\ &\text{Prefix}[i]-\text{Prefix}[j-1]=k\\ \hline &\text{Prefix}[j-1]=\text{Prefix}[i-1]+\text{nums}[i]-k \end{align} $$

而哈希的作用就在于保证平均 $\mathrm O(1)$ 查找。

class Solution {
public:
  int subarraySum(vector<int>& nums, int k) {
    std::unordered_map<int, int> PrefixFreq{{0, 1}};

    int Count = 0, Prefix = 0;
    for (int X : nums) {
      Prefix += X;
      if (PrefixFreq.find(Prefix - k) != PrefixFreq.end())
        Count += PrefixFreq[Prefix - k];
      ++PrefixFreq[Prefix];
    }

    return Count;
  }
};

二刷

class Solution {
public:
  int subarraySum(vector<int>& nums, int k) {
    using Frequency = int;
    using PrefixSum = int;
    unordered_map<PrefixSum, Frequency> Map{{0, 1}};
    int Amount = 0;
    PrefixSum Prefix = 0;
    for (int X : nums) {
      Prefix += X;
      if (auto I = Map.find(Prefix - k); I != Map.end()) {
        if (I->second)
          Amount += I->second;
      }
      // Increase at the end to avoid false positives like nums = [1] and k = 0,
      // where premature increment can cause the Map to have an entry of {1, 1}.
      ++Map[Prefix];
    }
    return Amount;
  }
};

要注意，我们在这道题的计算当中，从来没有关注过单点的和，关注的全部都是前缀和！官方的图解说实话画得也不好，非常容易让人以为我们在考虑单点。事实上我们应该这样画图：

关于这道题用到的哈希+前缀和的技巧，事实上你可以发现，但凡需要实现 $\mathrm O(1)$ 查找，都可以用哈希表来实现；但凡需要实现 $\mathrm O(1)$ 计算，都可以用前缀和来实现。

三刷

class Solution {
  using prefix_t = int;
  using count_t = int;
public:
  int subarraySum(vector<int>& nums, int k) {
    int Result = 0;
    int Prefix = 0;
    unordered_map<prefix_t, count_t> Map{{0, 1}};
    for (int X : nums) {
      Prefix += X;
      Result += Map[Prefix - k];
      ++Map[Prefix];
    }
    return Result;
  }
};

题目解法不长，但是要千万注意循环当中三个语句的顺序。

首先更新前缀和，为接下来在Map当中查找做准备。注意，如同二刷里所说的那样，我们考察的永远是前缀和而不是单点和，所以查询语句的键是不可能包含X的。

然后查找Map里对应前缀和的频次。这里写得比二刷要简洁，因为其实这样写就可以了——就算触发了默认构造，构造出来的频次也是0，不会影响解题；

最后才是更新Map，避免像二刷注释当中写的那样的假阳性情况。