#Coding-Data View

数组/字符串-子数组/子串

数组和字符串中经常出现的一类问题是寻找某种性质的子数组或子串。它们是下标连续的一段内容，与子序列不同。

子数组与子串之间的区别是，子数组可以结合一些数学运算，比如求和，成绩，min/max等。而子串常见的问题就是字符出现的次数，连续的字符等。

常见的问题：

寻找满足某种性质的子数组/子串
- 最长/最短
- 求和/乘积(数组)
满足某种性质的子数组/子串的个数
- 最多K个
- 恰好K个

蛮力方法：

枚举所有子数组或者字符串

滑动窗口

53. Maximum Subarray

Max Contiguous Subarray Sum - Cubic Time To Kadane’s Algorithm (“Maximum Subarray” on LeetCode)

优化代码时考虑的3个要素：BUD

Bottlenecks
Unnecessary Work
Duplicate Work

152. Maximum Product Subarray

加法和乘法的区别：乘法可能由负数 * 负数变成最大的解决办法：有一个minToCur数组来保存截止到当前位置的最小值

713. Subarray Product Less Than K

当某个性质不满足时可以停在当前，并调整起始窗口的位置时，就可以考虑使用滑动窗口

而560. Subarray Sum Equals K 不满足这个性质，它不满足可以停在当前位置，所以要用别的方法

Prefix Sum

560. Subarray Sum Equals K 计数

在枚举子数组的时候，当前值超过K时，不能马上停止，因为后面有可能出现负数再把值减回来

1
2
3

[3 1 2 1 -1] K=3
[1] [1 2]=3 [1 2 1] [1 2 1 -1]

prefixSum array

prefixSum[x] = sum of array(0,x) = nums[0] + nums[1] + … + nums[x]

index: 0 1 2
nums: [1 1 1 ]
prefixSum[x] [0 1 2 3] (0是为了让原来数组中的每一subarray都能对应到prefixSum中的某两个元素的差)

sum of subarray(i, j)(i是可以取到0的) = prefixSum[j] - prefixSum[i-1]

prefixSum[j] = nums[0] + nums[1] + … + nums[i-1] + nums[i] + … + nums[j]
prefixSum[i-1] = nums[0] + nums[1] + … + nums[i-1]

e.g. sum of subarray(1,2) = prefixSum[2] - prefixSum[0]

有了prefixSum后问题就转化为：有多少对且i < j,prefixSum[j] - prefixSum[i] == k ?

1 2	for each j: how many i < j satisfies prefixSum[i] = prefixSum[j] - k

795. Number of Subarrays with Bounded Maximum

在计算子数组的个数时，比如小标为[i, j]。那么以j为结尾的子数组的个数为i-j+1个。

单调栈

907. Sum of Subarray Minimums

stack solution with very detailed explanation step by step

Subarrays of circular arrays

918. Maximum Sum Circular Subarray

问题会分为两种情况：

最大数组和在一个区间内 [i,j]
最大数组和在两个区间 [0, i] [j, n-1]

第一种情况已经解决过，第二种情况可以划分为选[i+1, j-1]中最小的和

有序子数组

581. Shortest Unsorted Continuous Subarray

Some equivalent mathematical models for describing a sorted array (assuming in ascending order). Suppose the given array is nums with length n, these models are as follows:

nums[k] <= nums[k + 1] for all 0 <= k < n - 1.
nums[k] == max[k] for all 0 <= k <= n - 1, where max[k] is the maximum value of the subarray nums[0, k].
nums[k] == min[k] for all 0 <= k <= n - 1, where min[k] is the minimum value of the subarray nums[k, n - 1].

The first model is the most common one (and probably the most familiar one) while the last two are less common. It’s easy to show that the second model is equivalent to the first by noting that for any index k < n - 1, we have max[k] <= max[k + 1], then nums[k] = max[k] <= max[k + 1] = nums[k + 1]. Similar results hold for the third model: nums[k] = min[k] <= min[k + 1] = nums[k + 1].

With these models in place, we can show that if indices i and j satisfy the following conditions, then nums[i, j] will be the shortest subarray we are looking for:

i is the smallest index such that nums[i] != min[i];
j is the largest index such that nums[j] != max[j].

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> minToEnd(n); 
        vector<int> maxFromStart(n);
        
        int curMin = INT_MAX;
        int curMax = INT_MIN;
        
        for(int i = n-1; i >= 0; i--)
        {
            curMin = min(nums[i], curMin);
            minToEnd[i] = curMin; 
        }
        
        for(int i = 0; i < n; i++)
        {
            curMax = max(nums[i], curMax);
            maxFromStart[i] = curMax;
        }
        
        int i = 0, j = n-1;
        while( i < n && nums[i] <= minToEnd[i]) ++i;
        while( j > i && nums[j] >= maxFromStart[j]) --j;
        
        return j - i + 1;
    }
};

1
2
3

[2 6 4 8 10  9  15] 原数组
[2 4 4 8  9  9  15] <- minToEnd // 如果和原数组保持不变，那这个数往右看都没有比它小的数        
[2 6 6 8 10 10  15] -> maxFromStart // 如果和原数组保持不变，那这个数往左看都没有比它大的数

单调栈也可以解决这个问题，两次遍历数组

第一次从左向右，递增用一个变量l保存弹出的下标，就是这个乱序元素本该在位置，尽量小 min
第二次从右向左，递减用一个变量r保存弹出的下标，就是这个乱序元素本该在位置，尽量大 max

r - l + 1就是这个数组的长度

prefix and postfix product

238. Product of Array Except Self

不用除法去做

借助左右乘积数组