투포인터 대표 문제
이 문제는 정렬이 안되어있지만 정렬이 되어있으면 투 포인터를 의심해봐야 한다.
import Foundation
var input = readLine()!.split(separator: " ").map({ Int(String($0))! })
var numbers = readLine()!.split(separator: " ").map({ Int(String($0))! })
var n = input[0]
var goal = input[1]
var end = 0
var sum = 0
var result = 0
for start in 0..<numbers.count {
while sum < goal && end < numbers.count {
sum += numbers[end]
end += 1
}
if sum == goal {
result += 1
}
sum -= numbers[start]
}
print(result)
이름 | 정렬 여부 | 윈도우 사이즈 | 이동 |
---|---|---|---|
투 포인터 | 대부분 O | 가변 | 좌우 포인터 양방향 |
슬라이딩 윈도우 | X | 고정 | 좌 또는 우 단방향 |