LeetCode 解题报告(167, 1, 15, 16, 18)--双指针解决ksum问题

ksum 问题是一类问题, 要求从给定的数字中找到k个数,使得这k个数的和等于特定值。题目不难,直观的方法的时间复杂度为 \(O(n^k)\), \(n\) 为给定的数字的个数, 关键在于时间复杂度的控制, 本文主要讲述通过双指针将这类问题的时间复杂度降为 \(O(n^{k-1})\)

下面将以 LeetCode 上的几道题目为例讲述这类问题: 167. Two Sum II - Input array is sorted 1. Two Sum 15. 3Sum 16. 3Sum Closest 18. 4Sum

之所以从 167. Two Sum II - Input array is sorted 开始讲述,是因为解决这个题目的思路就是解决这类问题的核心思想。

167. Two Sum II - Input array is sorted 这道题目的解决思路如下: 1)初始化双指针,left指针在最左端,right指针在最右端 2)计算left指针和right指针指向的两个数的和,如果大于目标和,右指针往左移动一步;如果小于目标和,左指针往右移动一步;如果等于目标和则返回 3) 重复 2)的操作直到两个指针相遇

上面的方法需要的前提条件是数字列表是有序的

实现的python代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
left, right = 0, len(numbers) - 1
while left < right:
tmp = numbers[left] + numbers[right]
if tmp > target:
right -= 1
elif tmp < target:
left += 1
else:
return [left+1, right+1]

通过上面的方法的思想可以解决这一类问题。

对于题目 1. Two Sum ,因为原来的数组数无序的,因此需要对数组先排序,而且由于要求返回的是下标而不是数字,因此也需要一个 HashTable 来存储原来数字的下标。时间复杂度为\((nlgn)\)

AC的python代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# O(nlgn) time, O(n) space, AC
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
inx = {}
for i in xrange(len(nums)):
inx.setdefault(nums[i], [])
inx[nums[i]].append(i)

nums.sort()
left, right = 0, len(nums) - 1
while left < right:
tmp = nums[left] + nums[right]
if tmp > target:
right -= 1
elif tmp < target:
left += 1
else:
return sorted([inx[nums[left]].pop(), inx[nums[right]].pop()])

对于题目 15. 3Sum ,也是需要先要对无序的数组进行排序,然后固定第一个数的下标,再用上面的双指针方法找到另外两个数;由于需要返回的是数字而不是下标,因此不需要一个 HashTable 来存储这些数字的下标。时间复杂度为\(O(n^2+nlgn)\),也就是\(O(n^2)\)

AC的python代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
i = 0
result = []
nums.sort()
while i<len(nums)-2:
if nums[i]>0:
break
else:
j = i+1
k = len(nums)-1
while j < k:
if nums[i]+nums[j]+nums[k]>0:
k-=1
elif nums[i]+nums[j]+nums[k]<0:
j+=1
else:
tmp = [nums[i],nums[j],nums[k]]
if tmp not in result:
result.append(tmp)
j+=1
k-=1
i+=1
return result

题目 16. 3Sum Closest15. 3Sum 思路一致,只是要找到与目标和最接近的和。时间复杂度也是 \(O(n^2)\)

AC的python代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return 0

nums.sort()
min = None
for i in range(len(nums)-2):
j = i+1
k = len(nums)-1
while j<k:
sum = nums[i]+nums[j]+nums[k]
if sum > target:
gap = abs(sum -target)
if min == None or min > gap:
min = gap
result = sum
k-=1
elif sum < target:
gap = abs(target - sum)
if min==None or min > gap:
min = gap
result = sum
j+=1
else:
result = sum
return result
return result

题目 18. 4Sum 的思路与上面的15. 3Sum, 只是一开始需要固定前两个数,然后通过双指针找到另外两个数,时间复杂度是\(O(n^3)\)。推广到 ksum 问题就是开始需要固定 k-2 两个数,然后通过双指针找到剩下的两个数。时间复杂度是\(O(n^{k-1})\)

AC的 python 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
result =[]
if len(nums) == 0:
return result

nums.sort()
for i in range(len(nums)-3):
for j in range(i+1,len(nums)-2):
m = j +1
n = len(nums)-1
while m < n:
sum = nums[i] + nums[j] + nums[m] + nums[n]
if sum>target:
n-=1
elif sum<target:
m+=1
else:
tmp = [nums[i],nums[j],nums[m],nums[n]]
if tmp not in result:
result.append(tmp)
m+=1
n-=1
return result