算法前缀和—Java版

前缀和概念

• 假设有数组 A=[1,2,3,4,5,6,7] 为原数组，有数组 B作为A的前缀和数组，那么B=[1,3,6,10,15,21,28]；可以发现B[i] = A[0]+....+A[i]，即B[i]是数组A的前面i个数的总和。可以前缀和表示如下公式：

  $$B[i]=\sum _{j=0}^{i}A[j]$$

• 因此有了前缀和数组可以简化我们算法就子区间和，假设没有前缀和要求数组A区间[2,4]的总和，我们需要从 i=2 遍历 到 i=4 ，时间复杂度为O(n)，通过前缀和只需要计算 B[4]-B[1]即可，因此可以将子区间和表示如下公式：B[i,j]=B[j]-B[i-1],j>=i 。但是上述子区间表示法在实际应用中会有问题，即当求区间B[0,j]的时候，会出现下标等于-1的情况，因此一般在程序中写成如下：

  $$B[i,j]=B[j]-B[i]+A[i]$$

递推构造前缀和

• 可以使用递推式构造前缀和，递推公式如下：

  $$B[i]=B[i-1]+A[i],B[0]=A[0]$$

不仅仅是这些

• 这些直接求前缀数字和的题目是前缀和最简单的题型，变换题型一般是记录前i个字符或者数组的状态，当遍历后续的i+k时求得前i+k的状态，然后比较两者之间的变化，推出中间长度k子串的状态看看是否满足题目要求。这才是前缀和的灵魂，前缀和一般和数组、子串、连续等关键字有关！！尤其是数组和字符串的问题，求最长子串，求数组满足条件的连续的最长长度！！！通过题目练习总结，尤其是最后两题！

LeetCode

• 560. 和为 K 的子数组

    public int subarraySum(int[] nums, int k) {int[] B = new int[nums.length];B[0] = nums[0];int count = 0;for (int i = 1; i < nums.length; i++) {B[i] = B[i-1]+nums[i];}for (int i = 0; i < nums.length; i++) {for (int j = i; j < nums.length; j++) {// 求i到j的前缀和，包括i和jint sum = B[j]-B[i]+nums[i];if(sum==k){count++;}}}return count;}
  

• 525. 连续数组

  一般而言，只用前缀和判断区间的复杂度为O(n^{2)，因为遍历区间复杂度就是O(n}2)，因此，往往使用哈希表来优化问题。前缀和+哈希表！
  如下，直接使用前缀和会导致超时！这道题需要把0变成-1，如果前i个数的和为-2，前i+7的和也是-2，那么巧了，那就意味着从i+1到i+7的和为0，即1和-1的数量一样多。这就是前缀的灵魂。

    public int findMaxLength(int[] nums) {int[] B = new int[nums.length];B[0] = nums[0];for (int i = 1; i < nums.length; i++) {B[i] = B[i-1]+nums[i];}int res = 0;for (int i = 0; i < nums.length; i++) {for (int j = i; j < nums.length; j++) {int sum = B[j]-B[i]+nums[i];if((j-i+1)==sum*2 && sum>res){res = sum;}}}return res;}
  

•  public int findMaxLength(int[] nums) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if(nums[i]==0){nums[i] = -1;}}int[] B = new int[nums.length];B[0] = nums[0];map.put(B[0],0);int maxx = 0;for (int i = 1; i < nums.length; i++) {B[i] = B[i - 1] + nums[i];if(!map.containsKey(B[i])){//只需要存第一个出现的值即可，因为求最长的，所以一定是第一个map.put(B[i],i);}else {//如果前面出现过int value = (i-map.get(B[i]));maxx = Math.max(value,maxx);}if(B[i]==0){maxx = Math.max(i+1,maxx);}}return maxx;}
  

1685. 有序数组中差绝对值之和

    public int[] getSumAbsoluteDifferences(int[] nums) {//使用一个规律，即数组是递增的，即后一个数的和与前一个数的和之间的关系//关系是，假设第i+1个数比第i个数大k，则i+1之后的数会在sum(i)的基础上少// (n-i+1)*k , 而i之前的数会在sum(i)的基础上多 (i-1)*kint n = nums.length;int[] res = new int[n];int sum = 0;for (int i = 0; i < n; i++) {sum+=(Math.abs(nums[i]-nums[0]))}res[0] = sum;for (int i = 1; i < n; i++) {int k = nums[i]-nums[i-1];int a = (i-1)*k;int b = (n-i-1)*k;res[i] = res[i-1]+a-b;}return res;}

1423. 可获得的最大点数

• 一开始秒想到动态规划，但是超时，正确思路是反过来找最小的剩下的连续序列。使用滑动窗口！

public int maxscore(int[] cardPoints,int left,int right,int k){if(k==1 && left<right){int value = Math.max(cardPoints[right],cardPoints[left]);map.put(""+left+right+k,value);return value;}int a = 0;int b = 0;if(map.containsKey(""+(left+1)+right+(k-1))){a = map.get(""+(left+1)+right+(k-1))+cardPoints[left];}else {a = maxscore(cardPoints,left+1,right,k-1)+cardPoints[left];}if(map.containsKey(""+left+(right-1)+(k-1))){b = map.get(""+(left)+(right-1)+(k-1))+cardPoints[right];}else {b = maxscore(cardPoints,left,(right-1),k-1)+cardPoints[right];}return Math.max(a,b);}public int maxScore(int[] cardPoints, int k) {//动态规划map = new HashMap<>();return maxscore(cardPoints,0,cardPoints.length-1,k);}

正确解法：

public int maxScore(int[] cardPoints, int k) {int n = cardPoints.length-k;int[] B = new int[cardPoints.length];B[0] = cardPoints[0];for (int i = 1; i < cardPoints.length; i++) {B[i] = B[i-1]+cardPoints[i];}if(cardPoints.length==k){return B[cardPoints.length-1];}int minn = Integer.MAX_VALUE;for (int i = 0; i <= k; i++) {int sum = B[i+n-1]-B[i]+cardPoints[i];if(sum<minn){minn = sum;}}return B[cardPoints.length-1]-minn;}

1371. 每个元音包含偶数次的最长子字符串

525. 连续数组

• 为什么挂这两道题，因为如果想到了这两道题的前缀和才是真的入门了，首先说525题。这道题前面已经提过，这道题需要把0变成-1，如果前i个数的和为-2，前i+7的和也是-2，那么巧了，那就意味着从i+1到i+7的和为0，即1和-1的数量一样多。这就是前缀的灵魂。那么换成1371，要求五个字母出现都是偶数的最长子字符串的长度，那么5个字符的奇偶状态就有32种，因此，同理在前i个字符如果是 ‘a’，‘e’，‘i’， ‘o’，都是偶数，'u’是奇数，而前i+9个字符前三个是偶数，后两个是奇数，那么意味着什么？意味着从i+1到i+9的子串中有奇数个 ‘o’ 。这只是一个例子，所以需要使用前i+k的状态与前i的状态对比，才知道中间这k个字符是什么状态。因此，前缀和并一定是前面数字之和，也可以是状态的变化。通过后面i+k的状态与i的状态推出中间的状态。这就是前缀和的灵魂。

• class Solution {public int findTheLongestSubstring(String s) {int n = s.length();int[] pos = new int[1 << 5];Arrays.fill(pos, -1);int ans = 0, status = 0;pos[0] = 0;for (int i = 0; i < n; i++) {char ch = s.charAt(i);if (ch == 'a') {status ^= (1 << 0);} else if (ch == 'e') {status ^= (1 << 1);} else if (ch == 'i') {status ^= (1 << 2);} else if (ch == 'o') {status ^= (1 << 3);} else if (ch == 'u') {status ^= (1 << 4);}if (pos[status] >= 0) {ans = Math.max(ans, i + 1 - pos[status]);} else {pos[status] = i + 1;}}return ans;}
  }