Prefix and

Prefix and also known asAccumulated and, refers to summing all elements in the sequence from the starting position to the current position

prefixSum[0] = nums[0]
prefixSum[1] = nums[0] + nums[1]
prefixSum[2] = nums[0] + nums[1] + nums[2]
...
prefixSum[i] = nums[0] + nums[1] + ... + nums[i]

Sequence of problem solving

First find the prefix and pre
Determine whether the current pre-k is in hashmap and complete the counting
Finally add pre to hashmap

560. Subarray of sum is K

Note that the initial addition (0, 1) is added, and the number of times the prefix sum of record is 0 is 1

Key variable analysis (pre,mp,count, all global variables)

1. `pre`(Prefix and)

meaning: From the starting position of the array to the current positioniThe sum of all elements ofpre = nums[0] + nums[1] + ... + nums[i]。
effect: Convert subarrays and problems into differences in prefix sum. For example, subarraysnums[j..i]The sum ofpre[i] - pre[j]。

2. `mp`(Hash table)

meaning: The key is the value of the prefix sum, and the value is the number of times the prefix sum occurs.
effect: Quickly query the number of occurrences of historical prefix sums to determine whether there is a subarray that meets the conditions.

3. `count`(counter)

meaning: Records satisfying andkthe total number of subarrays.
effect: Accumulate all possible subarray combinations.

Official question answer:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        (0, 1);
        for (int i = 0; i < ; i++) {
            pre += nums[i];
            if ((pre - k)) {
                count += (pre - k);
            }
            (pre, (pre, 0) + 1);
        }
        return count;
    }
}

My first implementation:

You cannot use double pointers, because the data may contain negative numbers.

public int subarraySum(int[] nums, int k) {
    int res = 0;
    int[] preSum = new int[+1];
    preSum[0] = 0;
    for(int i=1;i<=;i++) {
        preSum[i] = preSum[i-1] + nums[i-1];
        for(int j=0;j<i;j++) {
            if(preSum[j] == preSum[i]-k) {
                res++;
            }
        }
    }
    return res;  
}

437. Path Sum III

【Solution 1: Two-fold traversal】

It is easy to think of a simple and direct two-step approach. The first step is to traverse all nodes, and the second step is to execute DFS with it as the root node on the current node, and find a path that meets the conditions with it as the starting point of the path. The following are three different implementations.

Version 1: BFS+DFS. The previous BFS is the first step and the next DFS is the second step.
Version 2: DFS+DFS. The first step is to examine the DFS implementation of each node's action, and the latter DFS effect remains unchanged.
Version 3: DFS+DFS with return value. In the previous two versions of the practice, the cumulative meter count is set as a class variable, and the path that meets the conditions is immediately accumulated in the DFS of the second step, without considering the return value. This version does not set class variables, but returns the number of paths that meet the requirements starting with the current node, layer by layer to root, and the final cumulative amount is given by root.

The version three with return value is a little more difficult to understand than the previous two versions, so I will explain it here. For each node node, the pathSum(node, targetSum) returns the value to represent the number of paths in the tree where this node is the root node. nodeSum(node, targetSum) calculates the number of path node values starting from node and the number of targetSum. That is, nodeSum(node, targetSum) = count + nodeSum(, targetSum - ) + nodeSum(, targetSum - ). For details, please refer to the "Code".

Time complexity: O(n^2), n is the number of nodes. A traversal is O(n), and for each node, up to O(n) nodes will be examined.
Space complexity: O(n), queue or stack depth.

// Version 1: BFS + DFS
 class Solution {
     int count, num, targetSum;
     public int pathSum(TreeNode root, int targetSum) {
         if(root == null) return 0;
          = targetSum;
         Queue<TreeNode> q = new ArrayDeque<>();
         (root);
         while(!()){ // BFS traverses all nodes
             TreeNode head = ();
             check(head, 0); // Check the number of paths that meet the requirements starting with the current node
             if( != null) ();
             if( != null) ();
         }
         return count;
     }
     private void check(TreeNode node, int sum){
         if(node == null) return;
         sum = sum + ;
         if(sum == targetSum) count++; // Once satisfied, accumulate immediately
         check(, sum);
         check(, sum);
     }
 }
 // Version 2: DFS + DFS (without return value)
 class Solution {
     int count, num, targetSum;
     public int pathSum(TreeNode root, int targetSum) {
         if(root == null) return 0;
          = targetSum;
         dfs(root); // DFS traverses all nodes
         return count;
     }
     private void dfs(TreeNode node){
         if(node == null) return;
         check(node, 0); // Check the number of paths that meet the requirements starting with the current node
         dfs();
         dfs();
     }
     private void check(TreeNode node, int sum){
         if(node == null) return;
         sum = sum + ;
         if(sum == targetSum) count++; // Once satisfied, accumulate immediately
         check(, sum);
         check(, sum);
     }
 }
 // Version 3: DFS + DFS (with return value)
 class Solution {
     public int pathSum(TreeNode root, int targetSum) {
         if(root == null) return 0;
         int count = nodeSum(root, targetSum);
         return count + pathSum(, targetSum) + pathSum(, targetSum);
     }
     private int nodeSum(TreeNode node, int targetSum){
         if(node == null) return 0;
         int count = 0, val = ;
         if(val == targetSum) count++;
         return count + nodeSum(, targetSum - val) + nodeSum(, targetSum - val);
     }
 }

[Solution 2: Prefix and]

There are many obvious repeated calculations in Solution 1, considering how to use the calculated information. Similar to finding the sum of continuous sub-arrays in an array as targetSum, this question also reflects the continuity from a certain point to a certain point on the parent-son link. This inspired us to use prefixes and methods to handle it. Use dfs to traverse the entire tree once, and calculate the prefix sum from root to the current node in real time. On the same path, the shorter prefix sum has been calculated. In order to find the difference between the prefix sum to find whether pre_i - pre_j = targetSum (pre_i is the prefix sum of the current node, and pre_j is the prefix sum of node j before the i node on the current path), we need to save the prefix sum of the previous node. map is an unthinkable choice. Key holds the prefix sum, and value holds the number of corresponding prefix sums. It should be noted that the object with the prefix and the difference is a node on the same path. Therefore, during the process of dfs traversing the tree, when the leaf node reaches and then returns upward, the path retreats, so that the current node will exit the subsequent path. The prerequisite for finding the difference between prefixes is to ensure that the prefixes saved in the map are the prefix sums of nodes on the same path, so the prefix sum represented by the node before returning needs to be deleted.

Time complexity: O(n), n is the total number of nodes, only one traversal is required.
Space complexity: O(n), map space.

// You can also use dfs with return value (the return value represents the accumulated amount to the current node position).
 // But in order to focus on the "prefix and sum" solution itself, the following implementation of dfs does not have a return value,
 // Using the class variable count, it is immediately accumulated when the prefix sum that meets the requirements is found.
 class Solution {
     int targetSum, count = 0;
     Map<Integer, Integer> map;
     public int pathSum(TreeNode root, int targetSum) {
         if(root == null) return 0;
          = targetSum;
          = new HashMap<>();
         (0, 1); // means that the node with the prefix sum is empty and there is one empty.  Otherwise, if pre_i = targetSum, the path from root to i will be missed.
         dfs(root, 0);
         return count;
     }
     private void dfs(TreeNode node, int preSum){
         if(node == null) return;
         preSum += ;
         count += (preSum - targetSum, 0); // #1 Cumulative prefixes and quantities that meet the requirements
         (preSum, (preSum, 0) + 1); // #2 Cumulative first and put (first #1, then #2)
         dfs(, preSum);
         dfs(, preSum);
         (preSum, (preSum) - 1); // Path retreats, removing the prefix sum of the current node that is no longer on the path.  Must exist, no need to use getOrDefault.
     }
 }

My answer: There is an example in the official test case. Using the int type will cause the value to cross the bounds, so it is changed to the Long type

class Solution {
	long targetSum;
	int count = 0;
	HashMap <Long,Integer> mp = new HashMap<>();
    public int pathSum(TreeNode root, long targetSum) {

    	 = targetSum;
    	if(root == null) {
    		return 0;
    	}
    	((long) 0,1);
    	dfs(root, 0);
    	return count;
        
    }
    public void dfs(TreeNode root,long preSum){
    	if(root==null) {
    		return;
    	}
    	preSum+=;
    	count+=(preSum-targetSum,0);
		(preSum, (preSum, 0)+1);
    	dfs(, preSum);
    	dfs(, preSum);
    	(preSum, (preSum)-1);
    	preSum-=;
    }
	
}

Prefix and

Prefix and

Sequence of problem solving

560. Subarray of sum is K

Key variable analysis (pre,mp,count, all global variables)

1. pre(Prefix and)

2. mp(Hash table)

3. count(counter)

Official question answer:

437. Path Sum III

1. `pre`(Prefix and)

2. `mp`(Hash table)

3. `count`(counter)