부품 편차 세 개로 목표 맞추기

문제

정밀 조립 라인에서는 각 부품의 무게를 기준값과 비교한 편차(단위 mg)를 기록합니다. 편차는 기준보다 무거우면 양수, 가벼우면 음수입니다.

품질팀은 창고에 있는 부품 중 서로 다른 세 개를 골라 편차의 합이 목표값 target과 정확히 일치하는 조합이 몇 가지인지 알고 싶어 합니다. 이때 편차 값의 구성이 같으면 같은 조합으로 봅니다. 예를 들어 편차가 -2인 부품이 두 개 있더라도 (-2, 0, 2) 조합은 어떤 부품을 골랐든 한 가지로 셉니다.

편차 배열 parts와 목표 합 target이 주어질 때, 조건을 만족하는 서로 다른 조합의 개수를 반환하는 solution(parts, target) 함수를 작성하세요.

예시

예시 1 설명: (1,4,7), (1,5,6), (2,3,7), (2,4,6), (3,4,5) 다섯 가지입니다.

예시 2 설명: (-2,-2,4)와 (-2,0,2) 두 가지입니다. 2가 두 개, -2가 두 개 있지만 값 구성이 같은 조합은 한 번만 셉니다.

제약 조건

• 0 ≤ parts.length ≤ 3,000
• -100,000 ≤ parts[i] ≤ 100,000, -300,000 ≤ target ≤ 300,000
• 같은 부품(같은 인덱스)을 두 번 고를 수 없습니다.
• 부품이 3개 미만이면 0을 반환합니다.

시간 복잡도 목표: O(n²)