https://www.sigmainfy.com/blog/summary-of-ksum-problems.html

2sum

  • 如果说是返回两个数,随便返回,那么sort一下,首尾两个指针一前一后一加一减就可以了

  • 如果是返回的index,那就不能sort了。需要用两重循环来做。注意题意。

3sum

[-1, 0, 1, 5]
首先认为这是一个搜索问题,需要遍历所有的值,当我们在第一个数的时候,需要解决什么问题
[-1, 0, 1, 5]
^
这个时候需要解决的问题,其实是2sum,也就是找到剩余数字中的数,使其他两个数的和为 0 - (-1),也就是1。这个时候其实就是一个2sum的问题

注意:

  • 最外层的数如何去重,只要确定i>0并且nums[i]!=nums[i-1]
  • 里面的如何去重,以及在什么时机去重。去重,应该在已经找到一个结果之后。并且确定仍然符合条件的时候去重。所以再while j<k 里面仍然有while j<k

其他人的解法,相当于复写了一个twosum

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution:
"""
@param: numbers: Give an array numbers of n integer
@return: Find all unique triplets in the array which gives the sum of zero.
"""

def threeSum(self, numbers):
# write your code here
result = []
if not numbers:
return result
length = len(numbers)
if length < 3:
return result
numbers.sort()
for i in xrange(0, length - 2):
# cause it's triple, so the outside loop should ensure it could not
# be equal with the previous one
# i > 0 是保证数组不会越最前面的界
# i > 0 ensure the array will not out of bound
if i > 0 and numbers[i] == numbers[i-1]:
continue
left, right = i+1, length-1
target = -numbers[i]
self.twoSum(numbers, left, right, target, result)
return result

def twoSum(self, numbers, left, right, target, result):
while left < right:
# take care of the loop reason
if numbers[left] + numbers[right] == target:
triple = []
# 因为是从小到大。所以 -target一定是最小
triple.append(-target)
triple.append(numbers[left])
triple.append(numbers[right])
result.append(triple)
left += 1
right -= 1

# 这里要保证里面的这层循环不要有重复
while left < right and numbers[left] == numbers[left - 1]:
left += 1
while left < right and numbers[right] == numbers[right + 1]:
right -= 1
elif numbers[left] + numbers[right] < target:
left += 1
else:
right -= 1

i,j,k版本

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
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""

result = []
if not nums:
return result
if len(nums) < 3:
return result
nums.sort()
for i in xrange(len(nums)-2):
if i!=0 and nums[i] == nums[i-1]:# 这个去重很重要
continue
j = i+1
k = len(nums)-1
while j < k:
if nums[j] + nums[k] == -nums[i]:
result.append([nums[i],nums[j],nums[k]])
j = j+1
k = k-1
while j < k and nums[j] == nums[j-1]: #这里,一定要在已经找到结果之后再加和减
j = j+1
while j < k and nums[k] == nums[k+1]:
k = k-1
elif nums[j] + nums[k] < -nums[i]:
j = j+1
else:
k = k-1
return result
  • 有关时间复杂度,虽然遍历一棵树,时间复杂度为O(n),但是这里并不是O(n),因为数的大小并不是n, 在3sum的时候如果用subsets的方式去解决。那么因为要找3个数,那么实际上是nn-1n-2 也就是O(n^3)的复杂度。
  • 上面的方法,实际上降到了O(n^2)的复杂度上。