[Algorithm] 1.PrefixSum

1.Prefix Sum : Sum Range Sum
leetcode:303

Prefix Sum involves preprocessing an array to create a new array where each element at index i represents the sum of the array from the start up to i. This allows for efficient sum queries on subarrays.

Use this pattern when you need to perform multiple sum queries on a subarray or need to calculate cumulative sums.

class NumArray {
    private prefixSum : number[] = [];
    constructor(nums: number[]) {
        
        for(let i = 0; i < nums.length; i++){
            this.prefixSum[i] = nums[i] + (this.prefixSum[i - 1] || 0);
        }
            
    }

    sumRange(left: number, right: number): number {
        if(left === 0) return this.prefixSum[right];
        return this.prefixSum[right] - (this.prefixSum[left - 1] || 0 );
    }
}

// usage 

const prefixSum = new NumArray([-2,0,3,-5,2,-1])
const result = prefixSum.sumRange(left, right);

2.PrefixSum maxLenth of Contiguous subarray

Leetcode:525

해설 geeksforgeeks

Youtube: neetcodeIO

7:30 ~ specific explanation.

function findMaxLength(nums: number[]): number {
	let zero = 0, one = 0;
    let maxLength = 0; 
	const map = new Map<number, number>() // <diff, index>
	for(const [i, n] of nums.entries()){
		if (n === 0) zero += 1;
        else one += 1;

       	if(!map.has(one - zero)) map.set(one - zero , i)
      	

		if(one === zero) {maxLength = one + zero}
        else{
			const idx = map.get(one - zero); 
   			maxLength = Math.max(maxLength, i - idx);
		} 
		
	}	
	return maxLength;
}

function findMaxLength(nums: number[]): number {
    let maxLength = 0; 
	let sum = 0; 
    const map = new Map<number, number>();
    map.set(sum, -1); // sum === 0; index === -1
    for(let i = 0 ; i < nums.length; i++){
        sum += nums[i] === 1 ? 1 : -1; 
        if(map.has(sum)){
            maxLength = Math.max(maxLength, i - map.get(sum));
        }else {
            map.set(sum, i);
        }
    }

    return maxLength; 
};

3.PrefixSum Subarray Sum Equals K

Leetcode:560

prefixSum

function subarraySum(nums: number[], k: number): number {
    let matched = 0; 
	let sum = 0; 
    let prefixSumMap = new Map<number, number>()
    prefixSumMap.set(sum, 1) // 초기값 저장 sum === 0 count + 1 
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
		const prefixNum = sum - k ; 
        if(prefixSumMap.has(prefixNum)){
            matched += prefixSumMap.get(prefixNum)!;
        }
        prefixSumMap.set(sum, (prefixSumMap.get(sum) || 0) + 1);
    }
    return matched;
}

해설

geeksforgeeks: better solution
Youtube

Why sum - k ? =>
sum = prefixSum + number;
prefixSum = sum - k;
prefixSumMap.get(prefixSum) -> how may values is (frequency)

Brute force 1

    let matched = 0; 
    
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j]; 
            if (sum === k) { 
                matched++;   
            }
        }
    }
	return matched;

Brute force 2

function subarraySum(nums: number[], k: number): number {
    const prefix = [];
    // prefix sum 
    for(let i = 0; i < nums.length; i++){
        prefix[i] = nums[i] + (prefix[i - 1]??0)
    }

    console.log(prefix)
    let cnt = 0;
   for(let end = 0 ; end < prefix.length; end++){
        if (prefix[end] === k) cnt++;
        for(let start = 0 ; start < end ; start++){
            if(prefix[end] - prefix[start] === k) cnt++
        } 
   }

return cnt;
}