Subarray Sum
Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.
S： DP O(n)
用hashmap存储已有的preSum
vector<int> subarraySum(vector<int> nums){
unordered_map<int, int> sumIdx;
vector<int> result;
int sum = 0;
sumIdx[0] = -1;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (sumIdx.find(sum) != sumIdx.end()) {
return vector<int> {sumIdx[sum] + 1, i};
}
sumIdx[sum] = i;
}
return vector<int>{};
}
Submatrix Sum
Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.
S1: DP O(n^4)
以submatrix右下角为用定位角，遍历左上角。
用preSum数组来避免重复的求和计算，和一维思路一样，只是不能用hashmap直接得到结果，必须遍历。
vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m < 1) {
return vector<vector<int>>{};
}
int n = matrix[0].size();
vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));
vector<vector<int>> result(2, vector<int>(2, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] +
matrix[i-1][j-1];
for (int k = 0; k < i; ++k) {
for (int p = 0; p < j; ++p) {
if ((k != i || p != j) &&
(preSum[k][j] + preSum[i][p] - preSum[k][p] == preSum[i][j])) {
result[0][0] = k;
result[0][1] = p;
result[1][0] = i - 1;
result[1][1] = j - 1;
return result;
}
}
}
}
}
return result;
}
S2：对列用preSum将问题转化为一维求解 O(n^3)
columSum[i][j]为第j列，i行及以上所有元素之和
vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) {
int m = matrix.size();
vector<vector<int>> result(2, vector<int>(2, 0));
if (m < 1) {
return result;
}
int n = matrix[0].size();
vector<vector<int>> columnSum(m + 1, vector<int>(n, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < n; ++j) {
columnSum[i][j] = columnSum[i-1][j] + matrix[i-1][j];
}
}
for (int row2 = 1; row2 <= m; ++row2) {
for (int row1 = 0; row1 < row2; ++row1) {
unordered_map<int, int> idx;
idx[0] = -1;
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += columnSum[row2][i] - columnSum[row1][i];
if (idx.find(sum) != idx.end()) {
result[0][0] = row1;
result[0][1] = idx[sum] + 1;
result[1][0] = row2 - 1;
result[1][1] = i;
return result;
}
idx[sum] = i;
}
}
}
return vector<vector<int>>{};
}
363. Max Sum of Rectangle No Larger Than K
Given a non-empty 2D matrixmatrixand an integerk, find the max sum of a rectangle in thematrixsuch that its sum is no larger thank.
Example:
Given matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2
The answer is2. Because the sum of rectangle[[0, 1], [-2, 3]]is 2 and 2 is the max number no larger than k (k = 2).
Note:
- The rectangle inside the matrix must have an area >0.
- What if the number of rows is much larger than the number of columns?
S: DP O(n*n*mlogm)
用submatrix化二维为1维找到每一列的行累计sum vector：rowsum (因为行数大于列数所以用行累计，否则也可用列累计)
问题转化为在rowsum中找到小于k的最大subarray sum，即cursum - presum <= k 可得presum >= cursum - k
将所有presum存入set可由lower.bound找到满足presum >= cursum - k的最大presum
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
int result = INT_MIN;
for (int col1 = 0; col1 < n; ++col1) {
vector<int> rowsum(m);
for (int col2 = col1; col2 < n; ++col2) {
for (int row = 0; row < m; ++row) {
rowsum[row] += matrix[row][col2];
}
set<int> sums;
sums.insert(0);
int curSum = 0;
for (int sum : rowsum) {
curSum += sum;
auto it = sums.lower_bound(curSum - k);
if (it != sums.end()) {
result = max(result, curSum - *it);
}
sums.insert(curSum);
}
}
}
return result;
}Subarray Sum II
Given an integer array, find a subarray where the sum of numbers is in a given interval. Your code should return the number of possible answers. (The element in the array should be positive)
S: preSum + search range O(nlogn)
因为数组中只有正数，preSum是个排序数组。
start <= preSum[i]-preSum[j] <= end 可得preSum[i]-end <= preSum[j] <= preSum[i]-start 用range search找到上限和下限
class Solution {
public:
int subarraySumII(vector<int>& A, int start, int end) {
int n = A.size();
if (n == 0) {
return 0;
}
vector<int> preSum(n + 1);
preSum[0] = 0;
int result = 0;
for (int i = 0; i < n; ++i) {
preSum[i + 1] = preSum[i] + A[i];
}
for (int i = 0; i < n; ++i) {
int startIdx = binarySearch(preSum, 0, i + 1, preSum[i + 1] - end, true);
int endIdx = binarySearch(preSum, 0, i + 1, preSum[i + 1] - start, false);
if (endIdx >= startIdx) {
result += endIdx - startIdx + 1;
}
}
return result;
}
private:
int binarySearch(vector<int>& A, int start, int end, int target, bool isLower) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] == target) {
return mid;
} else if (A[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if (isLower) {
if (A[start] >= target) {
return start;
} else if (A[end] >= target) {
return end;
} else {
return -1;
}
} else {
if (A[end] <= target) {
return end;
} else if (A[start] <= target) {
return start;
} else {
return -2;
}
}
}
};
34. Search for a Range
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order ofO(logn).
If the target is not found in the array, return[-1, -1].
For example,
Given[5, 7, 7, 8, 8, 10]and target value 8,
return[3, 4].
S: binary search O(logn）
两边二分查找找到起点和终点
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> result(2, -1);
int n = nums.size();
if (n == 0) {
return result;
}
int start = 0, end = n - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid;
} else {
start = mid;
}
}
if (nums[start] == target) {
result[0] = start;
} else if (nums[end] == target){
result[0] = end;
} else {
return result;
}
start = 0, end = n - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid;
} else {
end = mid;
}
}
if (nums[end] == target) {
result[1] = end;
} else if (nums[start] == target) {
result[1] = start;
}
return result;
}
325. Maximum Size Subarray Sum Equals k
Given an arraynumsand a target valuek, find the maximum length of a subarray that sums tok. If there isn't one, return 0 instead.
Note:
The sum of the entirenumsarray is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Givennums=[1, -1, 5, -2, 3],k=3,
return4. (because the subarray[1, -1, 5, -2]sums to 3 and is the longest)
Example 2:
Givennums=[-2, -1, 2, 1],k=1,
return2. (because the subarray[-1, 2]sums to 1 and is the longest)
S：hashmap存储已出现过的presum O(n)
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<int, int> preSum;
int sum = 0;
int result = 0;
preSum[0] = -1;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (preSum.find(sum - k) != preSum.end()) {
int dist = i - preSum[sum - k];
result = max(result, dist);
}
if (preSum.find(sum) == preSum.end()) {
preSum[sum] = i;
}
}
return result;
}