LeetCode 2824. Count Pairs Whose Sum is Less than Target
はじめに
LeetCode 「2824. Count Pairs Whose Sum is Less than Target」の問題をGoで解きました。
問題
問題文
Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.
和訳
長さ n のゼロインデックスの整数配列 nums と整数 target が与えられたとき、
0 <= i < j < n かつ nums[i] + nums[j] < target であるペア (i, j) の数を返す。
例
Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.
Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target
制約
- 1 <= nums.length == n <= 50
- -50 <= nums[i], target <= 50
解答1
まず、シンプルな方法を考えました。
numsの全ての組み合わせで合計がtargetよりも小さいものを数えていく方法です。
コード
func countPairs(nums []int, target int) int {
count := 0
for i := 0; i < len(nums)-1; i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i] + nums[j] < target {
count++
}
}
}
return count
}
外側のループで基準となるindexを定め、内側のループで基準となるindexよりも後ろの数との組み合わせを作っていきます。
以下のように組み合わせが作られます。
- (0,1),(0,2)...
- (1,2),(1,3)...
- (2,3),(2,4)...
計算量
- 時間的計算量：O(n²)
- 空間的計算量：O(1)
解答2
先ほどの例は、ソートされていない前提での解答でしたが、事前にソートすれば別のアプローチもできそうです。
例1のnums[-1,1,2,3,1]は、ソートすると[-1,1,1,2,3]となります。
ソート後のスライスの -1(nums[0])を基準に考えると、(0, 4)との組み合わせだと条件を満たしませんが、(0, 3)だと条件を満たします。
(0, 3)が条件を満たすことがわかれば、(0, 2)と(0, 1)も条件を満たすことになります。
コード
func countPairs(nums []int, target int) int {
slices.Sort(nums) // Go 1.21以前では sort.Ints(nums) を使用する
count := 0
left, right := 0, len(nums)-1
for left < right {
if nums[left]+nums[right] < target {
count += (right - left)
left++
} else {
right--
}
}
return count
}
Two Pointers パターンで実装しています。
基本的なTwo Pointers パターンについての解説は別の問題の記事で紹介していますので、参考をご覧ください。
実装の流れを以下で説明します。
例1のソート後のスライス[-1,1,1,2,3]を例とします。
leftとrightの初期値は(0, 4)となります。
[-1, 1, 1, 2, 3]
↑ ↑
left(0) right(4)
-1 + 3 = 2 なので、条件を満たしません。
これは、3が含まれる組み合わせの中で最小の組み合わせなので、3を含む他の組み合わせも条件を満たしません。
これ以上考慮する必要はないことからright--でポインタを動かしています。
次は(0, 3)となります。
[-1, 1, 1, 2, 3]
↑ ↑
left(0) right(3)
-1 + 2 = 1なので、条件を満たします。
スライスはソート済みなので、(0, 3)が条件を満たすということは(0, 2)と(0, 1)も条件を満たします。
条件を満たす数はright - leftで計算できます。
その後leftのポインタを移動して、同様の処理を繰り返していく流れです。
計算量
- 時間的計算量：O(n log n)
- ソート：O(n log n)
- Two Pointers: O(n)
- 空間的計算量：O(1)
参考
Two Pointers パターンを使用する別の問題を以下の記事で紹介しています。
Discussion