[LeetCode]Binary Subarrays With Sum

这道题有很多种方法，我们可以记录下所有的1对应的位置，然后计算所有和为S的子数组。比如对于数组[1,0,1,0,1]，其1所在的位置为[0, 2, 4]。那么S等于2的时候:

• [0, 2-3]满足条件
• [1-2, 4]满足条件

每次我们check 区间和等于S的可能的子区间的左边界和右边界的范围，从最左边满足条件的位置开始，一步一步向右边计算即可。时间空间复杂度均为O(N)，代码如下:

	class Solution {
	public:
	int numSubarraysWithSum(vector<int>& A, int S) {
	int len = A.size();
	vector<int> idxs;
	for (int i = 0; i < len; ++i)
	if (A[i] == 1)idxs.push_back(i);
	if (idxs.size() < S)return 0;
	idxs.push_back(len);
	int left = 0, right = S, res = 0;
	while (right < idxs.size())
	{
	int leftLen = left ? idxs[left] - idxs[left - 1] : idxs[left] + 1, rightLen = right? idxs[right] - idxs[right - 1]: idxs[right] + 1;
	res += S ? leftLen * rightLen : leftLen * (leftLen - 1) / 2;
	++left;
	++right;
	}
	return res;
	}
	};

view raw Binary Subarrays With Sum_1.cpp hosted with ❤ by GitHub

另一种方法就是presum，每次我们看有多少前缀和等于currPreSum - S的即可。时间空间复杂度均为O(N)，代码如下:

	class Solution {
	public:
	int numSubarraysWithSum(vector<int>& A, int S) {
	int len = A.size(), sum = 0, res = 0;
	unordered_map<int, int> presums;
	++presums[0];
	for (int i = 0; i < len; ++i)
	{
	sum += A[i];
	res += presums[sum - S];
	++presums[sum];
	}
	return res;
	}
	};

view raw Binary Subarrays With Sum_2.cpp hosted with ❤ by GitHub

我们还有一种不需要额外空间的解法，就是双指指针。但是这里只有两个指针是不够的，对于以j结尾的数组，我们还需要另外两个指针:

• lo表示[lo, j]的和等于S的最小index
• hi表示[hi, j]的和等于S的最大index

这样每次对于j结尾的子数组，满足条件的有hi - lo  +1个。时间复杂度O(N)，常数空间，代码如下:

	class Solution {
	public:
	int numSubarraysWithSum(vector<int>& A, int S) {
	//lo smallest idx where sum[lo, i] == S
	//hi largest idx where sum[i, hi] == S
	int len = A.size(), lo = 0, hi = 0, sumLo = 0, sumHi = 0, res = 0;
	for (int i = 0; i < len; ++i)
	{
	sumLo += A[i];
	sumHi += A[i];
	while (sumLo > S && lo < i)sumLo -= A[lo++];
	while ((sumHi > S || sumHi == S && !A[hi]) && hi < i)sumHi -= A[hi++];
	if (lo <= i && sumLo == S)res += hi - lo + 1;
	}
	return res;
	}
	};

view raw Binary Subarrays With Sum_3.cpp hosted with ❤ by GitHub