문제설명
길이가 0부터 시작하는 정수 배열 과 정수가 주어 지면 및 쌍의 개수를 반환합니다 . numsntarget (i, j) 0 <= i < j < n nums[i] + nums[j] < target
예시 1:
입력: nums = [-1,1,2,3,1], target = 2
출력: 3
설명: 명령문의 조건을 충족하는 인덱스 쌍이 3개 있습니다.
0 < 1이므로 - (0, 1) 및 nums[0] + nums[1] = 0 < target
- (0, 2) 왜냐하면 0 < 2이고 nums[0] + nums[2] = 1 < target
- (0, 4) 왜냐하면 0 < 4이고 nums[이기 때문입니다. 0] + nums[4] = 0 < 목표
nums[0] + nums[3]이 목표보다 엄격하게 작지 않기 때문에 (0, 3)은 계산되지 않습니다.
예 2:
입력: nums = [-6,2,5,-2,-7,-1,3], target = -2
출력: 10
설명: 명령문의 조건을 만족하는 인덱스 쌍이 10개 있습니다:
- (0 , 1) 0 < 1 및 nums[0] + nums[1] = -4 < target
- (0, 3) 이후 0 < 3 및 nums[0] + nums[3] = -8 < target
- (0 , 4) 0 < 4 및 nums[0] + nums[4] = -13 < target
- (0, 5) 이후 0 < 5 및 nums[0] + nums[5] = -7 < target
- (0 , 6) 0 < 6 및 nums[0] + nums[6] = -3 < target
- (1, 4) 이후 1 < 4 및 nums[1] + nums[4] = -5 < target
- (3) , 4) 3 < 4 및 nums[3] + nums[4] = -9 < target
- (3, 5) 이후 3 < 5 및 nums[3] + nums[5] = -3 < target
- (4) , 5) 4 < 5 및 nums[4] + nums[5] = -8 < target
- (4, 6) 이후 4 < 6 및 nums[4] + nums[6] = -4 < target
class Solution:
def count_pairs(self, nums, target):
nums.sort() # 배열을 정렬합니다.
n = len(nums)
count = 0
# 투 포인터를 이용하여 합이 target보다 작은 쌍의 개수를 세기
left = 0
right = n - 1
while left < right:
if nums[left] + nums[right] < target:
# nums[left]와 nums[right]를 포함하는 쌍들의 개수는 right - left입니다.
count += right - left
left += 1 # 더 작은 값을 만들기 위해 왼쪽 포인터를 오른쪽으로 이동합니다.
else:
right -= 1 # 합이 target 이상이면 더 큰 값으로 이동합니다.
return count<내 코드의 흐름>
1. countPairs라는 메서드를 정의합니다. 이 메서드는 nums와 target 두 개의 매개변수를 받습니다. 이 메서드는 Solution 클래스의 인스턴스 메서드이므로 첫 번째 매개변수로 self를 받습니다.
2. sort()를 이용해 주어진 nums 리스트를 오름차순으로 정렬합니다.
3. 리스트의 길이를 변수 n에 저장합니다.
4.조건을 만족하는 쌍의 개수를 저장할 변수 count를 초기화합니다.
5. 왼쪽 포인터를 배열의 첫 번째 인덱스로 초기화합니다.
6. right = n - 1: 오른쪽 포인터를 배열의 마지막 인덱스로 초기화합니다.
7. while left < right: 왼쪽 포인터가 오른쪽 포인터보다 작은 동안 반복합니다.
8. 왼쪽 포인터와 오른쪽 포인터가 가리키는 값의 합이 target보다 작으면 아래 코드를 실행합니다.
9. count += right - left: 조건을 만족하는 쌍들의 개수를 right - left만큼 증가시킵니다. 왜냐하면 정렬된 배열에서 왼쪽 포인터가 고정된 상태에서 오른쪽 포인터가 이동하면서 조건을 만족하는 쌍들의 개수가 늘어나기 때문입니다.
10. left += 1: 왼쪽 포인터를 오른쪽으로 이동시켜 더 작은 값을 만듭니다.
11. else: 합이 target 이상이면 아래 코드를 실행합니다.
12. right -= 1: 오른쪽 포인터를 왼쪽으로 이동시켜 더 작은 값을 만듭니다.
13. return count: 조건을 만족하는 쌍의 개수인 count 값을 반환합니다.
