前缀和概念
-
假设有数组
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]=∑j=0iA[j]B[i]=\sum_{j=0}^{i}{A[j]} B[i]=j=0∑iA[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,j]=B[j]-B[i]+A[i] B[i,j]=B[j]−B[i]+A[i]
递推构造前缀和
-
可以使用递推式构造前缀和,递推公式如下:
B[i]=B[i−1]+A[i],B[0]=A[0]B[i]=B[i-1]+A[i],B[0]=A[0] 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(n2),因为遍历区间复杂度就是O(n2),因此,往往使用哈希表来优化问题。前缀和+哈希表!
如下,直接使用前缀和会导致超时!这道题需要把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;} }