Prefix Sum

참조 : 이것이 취업을 위한 코딩 테스트다 (나동빈 저)

• 숫자가 들어있는 어떤 배열에 대해서, 인덱스 i부터 인덱스 j까지의 부분 합을 구할 때 사용하는 알고리즘.
• 매번 길이를 지정해서 매번 빼 주면, 시간이 너무 오래 걸리게 된다. 그러므로 구간별 합을 나타내는 배열을 새로 만들어 준다.
• 합을 저장할 배열을 [0]으로 만든 다음, 처음부터 해당 인덱스까지의 합을 차례로 저장해 준다.
• 인덱스 i부터 인덱스 j까지의 합을 구하고자 한다면(i<j), sums[j] - sums[i-1]을 구하면 된다.
• 예시를 위한 코드. LeetCode No.560의 풀이이며, Swift로 작성되었다.

class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var sums = [0]
        var index = nums.startIndex
        while index < nums.count {
            sums.append(nums[index] + sums[index])
            index = nums.index(after: index)
        }
        
        var result = 0
        
        var addLength = 0
        while addLength < sums.count {
            for j in 0..<sums.count - addLength - 1 {
                let left = j
                let right = j + addLength + 1
                if sums[right] - sums[left] == k {
                    result += 1
                }
            }
            
            addLength += 1
        }
        
        return result
    }
}