# SubArray + HashMap

## **Subarray Sum Equal Zero**

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. Example Given \[-3, 1, 2, -3, 4], return \[0, 2] or \[1, 3].

* If we find that a running sum value at index j has been previously seen before in some earlier index i in the array, then we know that the sub-array (i,j] contains a desired sum

```java
public ArrayList<Integer> subarraySum(int[] nums) {
    ArrayList<Integer> ans = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();

    map.put(0, -1);

    int sum = 0;
    for (int i = 0; i < nums.length; i++){
        sum += nums[i];
        if (map.containsKey(sum)){
            ans.add(map.get(sum) + 1);
            ans.add(i);
            return ans;
        }
        map.put(sum, i);
    }
    return ans;
```

## 325. Maximum Size Subarray Sum Equals K

1. 用hashmap 紀錄到當前idx每個idx的presum, 如果能找cur sum - previous sum == k update max
2. presum只需update第一次出現的地方

```python
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
    sum = 0
    # base case
    record = {0:-1}
    ans = 0
    
    for i, n in enumerate(nums):
        sum += n
        if sum-k in record:
            ans = max(ans, i-record[sum-k])
        if sum not in record:
            record[sum] = i       
    return ans
```

## 560 Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

1. Time O(n), Space O(n)

```
Input:nums = [1,1,1], k = 2
Output: 2
```

用hashmap 紀錄到當前idx每個idx的presum, 如果能找cur sum - previous sum == k update count

```python
def subarraySum(self, nums: List[int], k: int) -> int:
    count, sum = 0, 0
    record = defaultdict(int)  # {sum : occur times}
    record[0] = 1
    
    for n in nums:
        sum += n
        if sum-k in record:
            count += record[sum-k]
        record[sum] += 1
    return count
```

## 525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

```python
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
```

參考subarray sum equal to k, k 改為0, 用sum, 1 遞增 0遞減, 只要count的number 曾經出現過代表上個index到當前index有相同數字的0,1 用一個hashmap紀錄count的index, 如果count在map裡就update max\_len

```python
def findMaxLength(self, nums: List[int]) -> int:
    max_len = 0
    sum = 0
    record = {0:-1}
    
    for i, n in enumerate(nums):
        sum += 1 if n else -1
        if sum in record:
            max_len = max(max_len, i - record[sum])
        else:
            record[sum] = i  
    return max_len
```

## 523 Continuous Subarray Sum Equals To n\*k

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n\*k where n is also an integer.

Time O(n^2), Space O(1)

```java
public boolean checkSubarraySum(int[] nums, int k) {
    for(int i=0; i<nums.length; i++){
        int sum=nums[i];
        for(int j=i+1; j<nums.length; j++){
            sum+=nums[j];
            if((k == sum) || k !=0 && sum%k == 0) return true;
        }
    }
    return false;
}
```

Time O(n), Space O(n)

Loop over array. Use a hashamp to record the (residue, idx). If we can see the residue in map, means the sum of numbers between i and j satisfied multiple of k&#x20;

```python
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    dic = {}
    dic[0] = -1
    s = 0
    
    for i, n in enumerate(nums):
        s += n
        if k!= 0:
            s %= k
        if s in dic:
            if i - dic[s] >= 2:
                return True
        else:
            dic[s] = i
    return False
```

## 437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

```python
class Solution:
    count = 0
    record = collections.defaultdict(int)
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.record[0] = 1
        self.helper(root, 0, sum)
        return self.count
    
    def helper(self, node, preSum, s):
        if not node:
            return 0
        
        preSum += node.val
        if preSum-s in self.record:
            self.count += self.record[preSum - s]
            
        self.record[preSum] += 1    
        self.helper(node.left, preSum, s)
        self.helper(node.right, preSum, s)
        self.record[preSum] -= 1
```

##


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/array/subarray/subarray-+-hashmap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.