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
16class 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
28class 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 Closest 与 15. 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
33class 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
29class 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