SubArray + HashMap

Use hashmap to record count/index. Must init base case {0: -1} or {0: 1}

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

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第一次出現的地方

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

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.

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

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)

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

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).

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