Prefix and
Today, let’s talk about a simple but very clever algorithm problem: calculate a subarray with several sums of k.
Then I will exhaust all the sub-arrays, calculate their sum, and see whose sum is equal to k.
The key is, ** how to quickly get the sum of a subarray **, for example, give you an array’nums’, let you implement an interface’sum (i, j) ‘, this interface to return’nums [i… j]’ and will be called multiple times, how do you implement this interface?
Since the interface needs to be called multiple times, it is obviously impossible to traverse’nums [i… j] ‘every time. Is there a fast way to calculate’nums [i… j]’ in O (1) time? This requires ** prefixes and ** tricks.