Prefix Sum
525. Contiguous Array
Approach:
Optimization:

As a matter of fact, we don’t need to use an array to store the prefix sum. Note that in the previous solution, only
presum[i]
is used in each iteration, so we can simply use a variable to store the latest prefix sum. 
There is also another trick to simplify the code. Notice that the
if presum[i] == 0
was used to check the current prefix sum is 0. This particaular case can be merged by initializingmemo
withmemo = {0: 1}
. In this casepresum[i] == 0
is equivalent topresum[i] in memo
andi+1
is identical toi  memo[presum[i]]
.
The final version
523. Continuous Subarray Sum
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13
Output: false
Approach: