Funcia
Lv.2arrayhashtwo-pointers

합이 T인 세 수 고르기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 nums와 정수 target이 주어집니다. 서로 다른 세 인덱스 i < j < k를 골라 nums[i] + nums[j] + nums[k] == target이 되는 경우가 몇 가지인지 반환하세요.

값이 같더라도 인덱스가 다르면 다른 경우로 셉니다.

입출력 예

numstargetresult
[1, 2, 3, 4, 5]92
[0, 0, 0, 0]04
[-1, 0, 1, 2, -1, -4]03

입출력 예 설명

예 1 — 1+3+5와 2+3+4 두 가지입니다.

예 2 — 네 개의 0 중 세 개를 고르는 방법은 (43)=4\binom{4}{3} = 4가지입니다.

예 3 — 인덱스 기준으로 (0,1,2), (1,2,4)(둘 다 -1+0+1), (0,3,4)(-1+2-1)의 세 가지입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[], target: int) → long

제한 사항

  • 3≤3 \le nums.length ≤3,000\le 3{,}000
  • −100,000≤-100{,}000 \le nums[i] ≤100,000\le 100{,}000
  • −300,000≤-300{,}000 \le target ≤300,000\le 300{,}000
  • 답은 64비트 정수로 반환합니다(최대 (30003)≈4.5×109\binom{3000}{3} \approx 4.5 \times 10^9로 32비트 정수 범위를 넘습니다).

기대 복잡도

시간
O(N^2)
공간
O(N)

입출력 예

numstarget기대 출력
[1,2,3,4,5]92
[0,0,0,0]04
[-1,0,1,2,-1,-4]03

힌트

힌트

세 개를 다 고르는 대신 두 개를 고르고, 나머지 하나는 세어 두기로 바꿔 보세요.

가운데 인덱스 j를 왼쪽부터 옮기면서, j보다 왼쪽에 있는 값들의 개수를 해시 맵(또는 값 범위가 작으니 배열) left에 모아 둡니다.

for j in 0..n-1:
    for k in j+1..n-1:
        answer += left[target - nums[j] - nums[k]]
    left[nums[j]] += 1

i < j < k 순서가 자연스럽게 지켜져 중복 없이 셀 수 있습니다. 같은 값이 많을 때도 그대로 맞습니다.

target - nums[j] - nums[k]가 값의 범위를 벗어나면 개수는 0입니다. 배열을 쓸 때 인덱스 범위를 꼭 확인하세요.

복잡도 목표

세 인덱스를 모두 도는 O(N3)O(N^3) 풀이는 효율성 테스트에서 시간 초과가 납니다. O(N2)O(N^2)이 필요합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness409판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.