[2143] 두 배열의 합

1. BF

2. 투포인터
 1) 양쪽의 부분합을 구한다.
 2) 정렬
 3) 투포인터로 target을 찾아간다.

// BF
let target = Int(String(readLine()!))!
var n = Int(String(readLine()!))!
let nArr = readLine()!.split(separator: " ").map{Int(String($0))!}
var m = Int(String(readLine()!))!
let mArr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dict = [Int:Int]()
var cnt = 0

for i in 0..<n{			// 순열
    for j in i..<n{
        let sum = nArr[i...j].reduce(0, +)
        dict[sum, default: 0] += 1
    }
}
for i in 0..<m{
    for j in i..<m{
        let sum = mArr[i...j].reduce(0, +)
        cnt += dict[target - sum, default: 0]
        
    }
}
print(cnt)

// 투포인터
let target = Int(readLine()!)!
let n = Int(readLine()!)!
let nArr = readLine()!.split(separator: " ").map {Int(String($0))!}
let m = Int(readLine()!)!
let mArr = readLine()!.split(separator: " ").map {Int(String($0))!}
var sumN = [Int]()
var sumM = [Int]()
var s = 0
var e = 0
var cnt = 0

for i in 0..<n {          // 순열
    sumN.append(nArr[i])
    for j in i+1..<n {
        sumN.append(sumN.last! + nArr[j])
        
    }
}
for i in 0..<m {
    sumM.append(mArr[i])
    for j in i+1..<m {
        sumM.append(sumM.last! + mArr[j])
    }
}
sumN.sort()				// 정렬
sumM.sort()				// 1. 정렬돼 있어야 투포인터 가능.
e = sumM.count-1		// 2. 연속되는 원소를 구하기 위해.

while s < sumN.count, 0 <= e {
    let sum = sumN[s] + sumM[e]
    if sum == target {
        let valueN = sumN[s]
        let valueM = sumM[e]
        var cntN = 0
        var cntM = 0
        
        while s < sumN.count, sumN[s] == valueN {	// 연속되는 원소 카운트
            cntN += 1
            s += 1
        }
        while 0 <= e, sumM[e] == valueM {
            cntM += 1
            e -= 1
        }
        cnt += cntN * cntM
    }
    else if sum < target {
        s += 1
    }else {
        e -= 1
    }
}
print(cnt)