My Blog | 详情

1.leetcode560.求数组中和为 k 的子数组个数

原题地址：https://leetcode.com/problems/subarray-sum-equals-k/

分析：

如果暴力遍历，对每个 (i,j) 计算 sum(i,j)，那么复杂度接近 O(n^3)，明显会超时。
如果维护一个数组 prefixSum[i]，它记录 [0,i] 的累加和，然后对于 (i,j) 我们只需计算 prefixSum(j) - prefixSum[i - 1] 即为 sum(i,j)，此时的复杂度为 O(n^2)。
进一步转换思路，每当遍历到 nums[j] 时，我如果知道在 [0, j - 1] 中，有多少个 [0, t], 使得 sum(0, t) = sum(0, j) - target, 那么 (t + 1, j) 就等于： sum(t + 1, j) = sum(0, j) - sum(0, t) = target, 即为满足条件的一个子序列 (t + 1, j)。所以为了达到这个目的，我们只需记录一个 hashmap, 它记录从 (0, 0) 到 (0, j) 中所有出现过的 sum 的次数。

两个方法的完整代码如下：

Solution 1: O(n^2)

// Solution 1: O(n^2)
// AC: Runtime: 1558 ms, faster than 5.00% of Java online submissions for Subarray Sum Equals K.
// Memory Usage: 41.2 MB, less than 87.24% of Java online submissions for Subarray Sum Equals K.
// record the accumulated sum of nums, and for two loops check whether sum equal to k.
// T:O(n^2), S:O(n)
// 
class Solution {
    public int subarraySum(int[] nums, int k) {
        int size = nums.length, tempSum = 0, ret = 0;
        int[] sum = new int[size + 1], maxSum = new int[size + 1], minSum = new int[size + 1];
        sum[0] = 0;
        maxSum[0] = 0;
        minSum[0] = 0;
        for (int i = 0; i < size; i++) {
            tempSum += nums[i];
            sum[i + 1] = tempSum;
            if (nums[i] >= 0) {
                maxSum[i + 1] = Math.max(sum[i + 1], nums[i]);
                minSum[i + 1] = minSum[i];
            } else {
                maxSum[i + 1] = maxSum[i];
                minSum[i + 1] = Math.min(sum[i + 1], nums[i]);
            }
        }

        for (int i = 0; i < size; i++) {
            if (maxSum[i + 1] + 1000 * (size - 1 - i) < k || minSum[i + 1] - 1000 * (size - 1 - i) > k) {
                continue;
            }
            for (int j = i; j < size; j++) {
                if (sum[j + 1] - sum[i] == k) {
                    ret++;
                }
            }
        }

        return ret;
    }
}

Solution 2: O(n)

// Solution 2: O(n), prefixSum + hashmap
// AC: Runtime: 17 ms, faster than 96.08% of Java online submissions for Subarray Sum Equals K.
// Memory Usage: 41 MB, less than 93.12% of Java online submissions for Subarray Sum Equals K.
// using prefixSum and hashmap to check how many range (i, j) prefixSum diff is equal to k
// T:O(n), S:O(n)
// 
class Solution {
    public int subarraySum(int[] nums, int k) {
        int size = nums.length, tempSum = 0, ret = 0;
        HashMap<Integer, Integer> sumCount = new HashMap<>();
        sumCount.put(0, 1);
        for (int i: nums) {
            tempSum += i;
            if (sumCount.containsKey(tempSum - k)) {
                ret += sumCount.get(tempSum - k);
            }
            if (sumCount.get(tempSum) != null) {
                sumCount.put(tempSum, sumCount.get(tempSum) + 1);
            } else {
                sumCount.put(tempSum, 1);
            }
        }

        return ret;
    }
}

2. leetcode1248. 求奇数个数为 k 的子数组个数：

原题地址：https://leetcode.com/problems/count-number-of-nice-subarrays/

解法详见：https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/1385497/Java-O(n)-code-or-prefix-sum-or-easy-understanding

思路：前缀和，只不过这里记录的是 [0, j] 的子数组中的奇数元素的个数，思路一样

完整代码：

// AC:: Runtime: 36 ms, faster than 26.88% of Java online submissions for Count Number of Nice Subarrays.
// Memory Usage: 47 MB, less than 95.84% of Java online submissions for Count Number of Nice Subarrays.
// same thought as prefixSum, see @ https://leetcode.com/problems/subarray-sum-equals-k/discuss/1380435/O(n2)-and-O(n)-or-Two-java-solutions-with-annotation
// T:O(n), S:O(n)
//
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int ret = 0, size = nums.length;
        int oddCountSum = 0;
        HashMap<Integer, Integer> record = new HashMap<>();
        record.put(0, 1);
        for (int num : nums) {
            if (num % 2 == 1) {
                oddCountSum++;
            }

            if (record.get(oddCountSum - k) != null) {
                ret += record.get(oddCountSum - k);
            }

            record.merge(oddCountSum, 1, Integer::sum);
        }

        return ret;
    }
}

3.leetcode974. 求和能被 k 整除的子数组的个数：

https://leetcode.com/problems/subarray-sums-divisible-by-k/

思路：一样可以用前缀和来达到 O(n) 复杂度的求解。我们定义一个 hashMap 用来记录前 i - 1 个元素所组成的任意子数组的和，mod k 之后的值的个数。这样遍历到第 i 个数时，只需检测 hashMap 中有无和当前 [0, i] 数组和 mod k 的余数相等，或者等于 mod - k, mod + k 的个数。注意这里要考虑 mod - k 和 mod + k , 因为数组元素可能为负，而为负的情况如果某个前数组 [0, j] 的 mod k 余数位 mod - k 或 mod + k, 那么 [j + 1, i] 仍是满足条件的一个子数组。

完整代码如下：

```java
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int size = nums.length, tempSum = 0, ret = 0;
        // record the number after mod-k of prefix sums.
        HashMap<Integer, Integer> record = new HashMap<>();
        // empty array can contribute a zero.
        record.put(0, 1);

        for (int i = 0; i < size; i++) {
            tempSum += nums[i];
            int modRemain = tempSum % k;
            if (record.containsKey(modRemain)) {
                ret += record.get(modRemain);
            }
            if (record.containsKey(modRemain - k)) {
                ret += record.get(modRemain - k);
            }
            if (record.containsKey(modRemain + k)) {
                ret += record.get(modRemain + k);
            }
            record.merge(modRemain, 1, Integer::sum);
        }

        return ret;
    }
}

4.leetcode303. 范围查询数组

https://leetcode.com/problems/range-sum-query-immutable/

直接应用。

代码：

// AC: Runtime: 6 ms, faster than 100.00% of Java online submissions for Range Sum Query - Immutable.
// Memory Usage: 44.1 MB, less than 13.72% of Java online submissions for Range Sum Query - Immutable.
// prefix sum
// T:O(1), S:O(n)
//
class NumArray {
    private int[] prefixSum;

    public NumArray(int[] nums) {
        prefixSum = new int[nums.length + 1];
        prefixSum[0] = 0;
        int tempSum = 0, pos = 1;
        for (int i: nums) {
            tempSum += i;
            prefixSum[pos++] = tempSum;
        }
    }

    public int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
}

5.leetcode523. 判断和为k的整数倍的子数组是否存在

https://leetcode.com/problems/continuous-subarray-sum/

维护一个从 0-indexed 开始的和 sum，使用hashmap记录每次 sum%k 的值。记住初始化时需要添加（0，-1），不然会漏掉 case。然后遍历到某个 i 时，若当前 sum%k 在 hashmap 中有相等 key 值的记录，那么区间（j,i] 就是满足条件的子数组。注意题目要求子数组长度 >= 2，所以判断 i - j > 1.

完整代码：

// AC: Runtime: 14 ms, faster than 96.51% of Java online submissions for Continuous Subarray Sum.
// Memory Usage: 55.2 MB, less than 78.62% of Java online submissions for Continuous Subarray Sum.
// prefixSum
// T:O(n), S:O(k)
// 
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int size = nums.length, sum = 0;
        HashMap<Integer, Integer> modKRecord = new HashMap();
        modKRecord.put(0, -1);
        for (int i = 0; i < size; i++) {
            sum += nums[i];
            int mod = sum % k;
            if (modKRecord.containsKey(mod)) {
                if (i - modKRecord.get(mod) > 1) {
                    return true;
                }
            } else {
                modKRecord.put(mod, i);
            }
        }

        return false;
    }
}

6.求包含相同个数 0 和 1 的最长子数组的长度

https://leetcode.com/problems/contiguous-array/

思路：本题仍可用前缀和 + hashmap 来解决。关键点在于，当 0 和 1 个数相同时有什么特征？如果直接累加0，1 之和，那么对于相同的 sum，无法区分子数组中是否 0 和 1 个数相等，因为多加 1 个 0 也不影响累和，所以需要做一点转换：我们把 0 的元素赋值为 -1，累加时按 -1 算。这样当累加和为 0 时就必定有 0 和 1 的个数相等。然后一次遍历数组，如果当前 sum 和 hashmap 中的值相等，那么这中间的区间（j, i] 就是满足条件的区间了。

完整代码：

// AC: Runtime: 19 ms, faster than 88.59% of Java online submissions for Contiguous Array.
// Memory Usage: 48.6 MB, less than 88.89% of Java online submissions for Contiguous Array.
// prefix sum & hashmap
// T:O(n), S:O(n)
//
class Solution {
    public int findMaxLength(int[] nums) {
        int size = nums.length, sum = 0, ret = 0;
        HashMap<Integer, Integer> record = new HashMap<>();
        record.put(0, -1);
        for (int i = 0; i < size; i++) {
            if (nums[i] == 0) {
                sum += -1;
            } else {
                sum += 1;
            }
            if (record.containsKey(sum)) {
                ret = Math.max(ret, i - record.get(sum));
            } else {
                record.put(sum, i);
            }
        }

        return ret;
    }
}

7.求矩阵和不超过 k 的子矩阵的和最大值

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/

思路：直接应用，使用二维数组 topLeftSum[i][j] 表示从 [0,0] 到 [i-1, j-1] 的子矩阵和，那么 (x1, y1) 和 (x2, y2) 为对角定点的子矩阵和即为: subSum = topLeftSum[x2 + 1][y2 + 1] - topLeftSum[x2][y2 + 1] - topLeftSum[x2 + 1][y2] + topLeftSum[x2][y2];

复杂度：遍历复杂度为 m^2 * n^2

// AC: Runtime 177 ms Beats 91.58% 
// Memory 44.7 MB Beats 5.26%
// Prefix Sum
// T:O(m ^ 2 * n ^ 2), S:O(m * n)
// 
class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int row = matrix.length, col = matrix[0].length, ret = Integer.MIN_VALUE;
        int[][] rowSum = new int[row + 1][col + 1], topLeftSum = new int[row + 1][col + 1];
        for (int i = 0; i < row; i++) {
            int oneRowSum = 0;
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == k) {
                    return k;
                } else if (matrix[i][j] < k) {
                    ret = Math.max(ret, matrix[i][j]);
                }
                oneRowSum += matrix[i][j];
                rowSum[i + 1][j + 1] = oneRowSum;
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                topLeftSum[i + 1][j + 1] = topLeftSum[i][j + 1] + rowSum[i + 1][j + 1];
            }
        }
        for (int x1 = 0; x1 < row; x1++) {
            for (int y1 = 0; y1 < col; y1++) {
                for (int x2 = x1; x2 < row; x2++) {
                    for (int y2 = y1; y2 < col; y2++) {
                        int matrixSum = topLeftSum[x2 + 1][y2 + 1] - topLeftSum[x1][y2 + 1] - topLeftSum[x2 + 1][y1] + topLeftSum[x1][y1];
                        if (matrixSum == k) {
                            return k;
                        }
                        if (matrixSum < k) {
                            ret = Math.max(ret, matrixSum);
                        }
                    }
                }
            }
        }

        return ret;
    }
}

8.求数组中包含最大元素个数不超过 k 的子数组的个数

https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times

思路：我们记录从 0 到 i 位的子数组中的包含最大元素个数位 maxCount[i] 与最小的 Index 的记录关系： Map<Integer, Integer> maxCountToIndex （注意，maxCount 相同，我们只记录最小 index）从 0 index 开始遍历，记录当前累计的最大元素个数 countMax，当遍历到第 N 位时，

若此时 countMax < k，那么代表以当前元素为结尾的前缀数组，均无法构成满足条件的子数组，跳过往下走
若次数 countMax >= k，那么代表以当前元素为结尾的前缀数组中，是存在满足条件的子数组的，但会有多个。具体多少个呢，只需要拿到 maxCount = countMax - k + 1 的索引 maxCountToIndex.get(countMax - k + 1) 即可，这个代表从这个索引往前，所有的前缀数组（左端点往前走，右端点是当前遍历的第 N 个元素）均满足。那么最终结果，加上 maxCountToIndex.get(countMax - k + 1) + 1 即可。

复杂度：时间复杂度：O(n) 空间复杂度：O(n)

// AC: Runtime 28 ms Beats 13.98% of users with Java
// Memory 58.48 MB Beats 84.52% of users with Java
// Prefix sum.
// T:O(n), S:O(n)
// 
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int len = nums.length, maxElem = 0, countMax = 0;
        long ret = 0;
        HashMap<Integer, Integer> countMaxToMinIndex = new HashMap<>();
        countMaxToMinIndex.put(0, -1);
        for (int i : nums) {
            maxElem = Math.max(maxElem, i);
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] == maxElem) {
                countMax++;
            }
            countMaxToMinIndex.putIfAbsent(countMax, i);
            if (countMax >= k) {
                ret += countMaxToMinIndex.get(countMax - k + 1) + 1;
            }
        }

        return ret;
    }
}