Conditions
Prefix sum is a powerful pre-processing/ caching technique for algorithm problems. The idea is to calculate/store the consecutive totals of the elements in an array in O(n).
Questions
-
304
-
class NumMatrix { // To achieve O(1) time complexity for sumRegion, we can use a precomputation technique called prefix sum. We can calculate a 2D prefix sum matrix where each element in the matrix represents the sum of all elements in the rectangle defined by (0, 0) and (i, j). // For example, given the matrix: // [1, 2, 3] // [4, 5, 6] // [7, 8, 9] // The prefix sum matrix would be: // [1, 3, 6] // [5, 12, 21] // [12, 27, 45] private int[][] prefixSum; public NumMatrix(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; prefixSum = new int[m+1][n+1]; // Compute prefix sum matrix for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return prefixSum[row2+1][col2+1] - prefixSum[row1][col2+1] - prefixSum[row2+1][col1] + prefixSum[row1][col1]; } } /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix obj = new NumMatrix(matrix); * int param_1 = obj.sumRegion(row1,col1,row2,col2); */
-
-
325
-
class Solution { public int maxSubArrayLen(int[] nums, int k) { // create HashMap to store cumulative sum and its index as key-value pairs Map<Integer, Integer> map = new HashMap<>(); // initialize sum and maxLength int sum = 0, maxLength = 0; // loop through the array for (int i = 0; i < nums.length; i++) { // add current element to sum sum += nums[i]; // check if sum is equal to k if (sum == k) { maxLength = i + 1; // update maxLength } else if (map.containsKey(sum - k)) { maxLength = Math.max(maxLength, i - map.get(sum - k)); // update maxLength if necessary } // if sum is not in the map, add it with its index as the value if (!map.containsKey(sum)) { map.put(sum, i); } } // return maxLength return maxLength; } }
-
-
523
-
class Solution { public boolean checkSubarraySum(int[] nums, int k) { // Create a HashMap to keep track of the running sum and remainder // Initialize the HashMap with the first element of the array Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); // If the running sum is a multiple of k, we can assume the subarray starts at index -1 int sum = 0; // Initialize the running sum for (int i = 0; i < nums.length; i++) { sum += nums[i]; // Add the current element to the running sum int remainder = sum % k; // Calculate the remainder // If the remainder has been seen before and the difference between the // current index and the index where we first saw the remainder is at least 2, // then we have found a good subarray if (map.containsKey(remainder) && i - map.get(remainder) >= 2) { return true; } // Otherwise, add the current remainder and its index to the HashMap if (!map.containsKey(remainder)) { map.put(remainder, i); } } return false; // If no good subarray is found, return false } }
-
-
560
-
class Solution { public int subarraySum(int[] nums, int k) { int count = 0; // initialize the count of subarrays with sum k int sum = 0; // initialize the sum of subarray Map<Integer, Integer> map = new HashMap<>(); // create a HashMap to store the sum and its frequency map.put(0, 1); // add the initial sum 0 to the HashMap with frequency 1 for (int i = 0; i < nums.length; i++) { // iterate through the array sum += nums[i]; // add the current element to the sum if (map.containsKey(sum - k)) { // check if there is a subarray with sum k count += map.get(sum - k); // add the frequency of the sum-k subarray to the count } map.put(sum, map.getOrDefault(sum, 0) + 1); // add the current sum to the HashMap with frequency 1 } return count; // return the count of subarrays with sum k } }
-
-
930
-
class Solution { public int numSubarraysWithSum(int[] nums, int goal) { // create a hashmap to store cumulative sum and its frequency of occurrence HashMap<Integer, Integer> map = new HashMap<>(); // initialize cumulative sum and count int sum = 0, count = 0; // loop through the binary array for (int num : nums) { // calculate the cumulative sum sum += num; // if the current cumulative sum equals the goal, increment the count if (sum == goal) { count++; } // check if there is a subarray that sums up to the given goal if (map.containsKey(sum - goal)) { count += map.get(sum - goal); } // update the frequency of occurrence of the current cumulative sum map.put(sum, map.getOrDefault(sum, 0) + 1); } // return the count as the final result return count; } }
-
-
974
-
class Solution { public int subarraysDivByK(int[] nums, int k) { int[] count = new int[k]; // initialize an array to store counts of subarrays with different remainders after dividing by k count[0] = 1; // initialize the count of subarrays with remainder 0 to 1, count[i] stores the count of subarrays with remainder i when divided by k. int sum = 0, res = 0; for (int num : nums) { sum = (sum + num) % k; // calculate the prefix sum and its remainder after dividing by k if (sum < 0) sum += k; // handle negative remainders res += count[sum]; // add the count of subarrays with the same remainder to the result count[sum]++; // increment the count of subarrays with this remainder } return res; } }
-
-
1248
-
class Solution { public int numberOfSubarrays(int[] nums, int k) { int n = nums.length; int[] count = new int[n + 1]; // create an array to store the count of subarrays with i odd numbers count[0] = 1; // initialize the count of subarrays with 0 odd numbers to 1 int oddCount = 0; // initialize the count of odd numbers seen so far to 0 int res = 0; // initialize the result to 0 for (int i = 0; i < n; i++) { oddCount += nums[i] % 2; // increment the odd count if the current number is odd if (oddCount >= k) { res += count[oddCount - k]; // add the count of subarrays with k odd numbers } count[oddCount]++; // increment the count of subarrays with oddCount odd numbers } return res; } }
-
-
1314
-
class Solution { public int[][] matrixBlockSum(int[][] mat, int k) { int m = mat.length, n = mat[0].length; int[][] prefixSum = new int[m + 1][n + 1]; int[][] result = new int[m][n]; // Calculate prefix sum of each row for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixSum[i][j] = prefixSum[i][j - 1] + mat[i - 1][j - 1]; } } // Calculate prefix sum of each column for (int j = 1; j <= n; j++) { for (int i = 1; i <= m; i++) { prefixSum[i][j] += prefixSum[i - 1][j]; } } // Calculate answer for each cell for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int r1 = Math.max(0, i - k), c1 = Math.max(0, j - k); int r2 = Math.min(m - 1, i + k), c2 = Math.min(n - 1, j + k); int sum = prefixSum[r2 + 1][c2 + 1] - prefixSum[r2 + 1][c1] - prefixSum[r1][c2 + 1] + prefixSum[r1][c1]; result[i][j] = sum; } } return result; } }
-
-
363
-
class Solution { public int maxSumSubmatrix(int[][] matrix, int k) { int m = matrix.length; int n = matrix[0].length; int maxSum = Integer.MIN_VALUE; // Compute prefix sums matrix int[][] prefixSums = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixSums[i][j] = matrix[i - 1][j - 1] + prefixSums[i - 1][j] + prefixSums[i][j - 1] - prefixSums[i - 1][j - 1]; } } // Find maximum sum for (int i1 = 1; i1 <= m; i1++) { for (int i2 = i1; i2 <= m; i2++) { for (int j1 = 1; j1 <= n; j1++) { for (int j2 = j1; j2 <= n; j2++) { int sum = prefixSums[i2][j2] - prefixSums[i1 - 1][j2] - prefixSums[i2][j1 - 1] + prefixSums[i1 - 1][j1 - 1]; if (sum <= k && sum > maxSum) { maxSum = sum; } } } } } return maxSum; } }
-
-
1074
-
class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int count = 0; // Iterate over all possible pairs of rows for (int i = 0; i < m; i++) { int[] sum = new int[n]; // Create an array to store the cumulative sums of columns for (int j = i; j < m; j++) { Map<Integer, Integer> map = new HashMap<>(); // Create a hashmap to store the frequency of prefix sums int prefixSum = 0; map.put(0, 1); // Initialize the hashmap with a prefix sum of 0 with a frequency of 1 for (int k = 0; k < n; k++) { sum[k] += matrix[j][k]; // Update the cumulative sums of columns prefixSum += sum[k]; // Calculate the prefix sum if (map.containsKey(prefixSum - target)) { // Check if there is a previous prefix sum that is equal to prefixSum - target count += map.get(prefixSum - target); // Add the frequency of the previous prefix sum to the count } map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1); // Increment the frequency of the current prefix sum } } } return count; } }
-
Conclusion
「少种的少收，多种的多收,捐款会鼓励作者多创作以及教会福音传播!!」
少种的少收，多种的多收,捐款会鼓励作者多创作以及教会福音传播!!
使用微信扫描二维码完成支付
