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

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

分析:

  1. 如果暴力遍历,对每个 (i,j) 计算 sum(i,j),那么复杂度接近 O(n^3),明显会超时。
  2. 如果维护一个数组 prefixSum[i],它记录 [0,i] 的累加和,然后对于 (i,j) 我们只需计算 prefixSum(j) - prefixSum[i - 1] 即为 sum(i,j),此时的复杂度为 O(n^2)。
  3. 进一步转换思路,每当遍历到 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;
    }
}