数组和字符串小结

数组

常用解题方法：前缀和、滑动窗口

前缀和

原文链接：https://leetcode-cn.com/problems/find-pivot-index/solution/de-liao-qian-zhui-he-na-xie-shi-bei-wo-b-f8q2/

前缀和其实我们很早之前就了解过的，我们求数列的和时，Sn = a1+a2+a3+…an; 此时Sn就是数列的前 n 项和。例 S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2。所以我们完全可以通过 S5-S2 得到 a3+a4+a5 的值，这个过程就和我们做题用到的前缀和思想类似。我们的前缀和数组里保存的就是前 n 项的和。见下图

我们通过前缀和数组保存前 n 位的和，presum[1]保存的就是 nums 数组中前 1 位的和，也就是 presum[1] = nums[0], presum[2] = nums[0] + nums[1] = presum[1] + nums[1]. 依次类推，所以我们通过前缀和数组可以轻松得到每个区间的和。

例如我们需要获取 nums[2] 到 nums[4] 这个区间的和，我们则完全根据 presum 数组得到，是不是有点和我们之前说的字符串匹配算法中 BM,KMP 中的 next 数组和 suffix 数组作用类似。那么我们怎么根据 presum 数组获取 nums[2] 到 nums[4] 区间的和呢？见下图

好啦，我们已经了解了前缀和的解题思想了，我们可以通过下面这段代码得到我们的前缀和数组，非常简单

 for (int i = 0; i < nums.length; i++) {
      presum[i+1] = nums[i] + presum[i];
 }

好啦，我们开始实战吧。

724. 寻找数组的中心下标

二维数组

字符串