Leetcode K-sum解题思路

Posted on |

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

暴力求解

遍历每个元素n，都向后查找是否有等于target-n的元素的存在，有则直接返回索引。

  • 时间复杂度：$O(n^2)$，对于每个元素，都需要遍历后面的元素，花费时间O(n)。一共含有n个元素，所以时间复杂度是$O(n^2)$。
  • 空间复杂度：O(1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            for i in range(len(nums)):
                for j in range(i+1,len(nums)):
                    if nums[j]==target-nums[i]:
                        return [i,j]

One-pass Hash Table

用哈希表（字典）保存数字n和索引的映射。
遍历查找数字n与目标数target的“互补数”时只需查找dic[target-n]是否存在即可。

  • 时间复杂度：O(n)，仅需要遍历list中的n个元素。每次只需要在字典中查找花费时间O(1)
  • 空间复杂度：O(n)，额外的空间依赖于哈希表中保存的与元素个数
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic={}
        for i, n in enumerate(nums):
            if target-n in dic:
                return [dic[target-n],i]
            dic[n]=i

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

One-pass Hash Table

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic={}
        for i, n in enumerate(numbers):
            if target-n in dic:
                return [dic[target-n]+1,i+1]
            dic[n]=i

双指针

数组是升序数组，随后用两个变量指向数组的开头和结尾：分别指向nums[0]和nums[numsSize]。

  • 如果nums[low]+nums[high] < target，则说明low指向的数太小，需要往后移动；
  • 如果nums[low]+nums[high] > target，则说明high指向的数太大，需要前移
  • 当两者相等，遍历结束
    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:
                sum=numbers[left]+numbers[right]
                if sum<target:
                    left+=1
                elif sum>target:
                    right-=1
                else:
                    return [left+1,right+1]

15. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

基于2Sum & 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        length=len(nums)
        if length<3:
            return []

        nums.sort()
        res=set()
        for i, n in enumerate(nums[:-2]):
            if i!=0 and n==nums[i-1]:
                continue

            dic={}
            for x in nums[i+1:]:
                if -n-x in dic:
                    res.add((n, -n-x, x))
                else:
                    dic[x]=1
        return map(list,res)

基于2Sum & 双指针

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]]
        """
        length=len(nums)
        if length<3:
            return []

        nums.sort()                         # 先排序，才能使用双指针方法
        res=set()
        for i, n in enumerate(nums[:-2]):   # 遍历到倒数第3个元素
            if i!=0 and n==nums[i-1]:       # nums[i-1]和nums[i]相等，那组合方法就是一样的，不必再重复了
                continue

            left=i+1
            right=length-1
            target=-n

            while left<right:
                sum=nums[left]+nums[right]
                if sum<target:
                    left+=1
                elif sum>target:
                    right-=1
                else:
                    res.add((n,nums[left],nums[right]))
                    left+=1
                    right-=1
        return map(list,res)

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

双指针

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 threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length=len(nums)
        if length<3:
            return []

        nums.sort()
        res=sum(nums[:3])

        for i in range(length):
            left,right=i+1,length-1
            while left<right:
                s=sum((nums[i],nums[left],nums[right]))
                if abs(s-target)<abs(res-target):
                    res=s

                if s<target:
                    left+=1
                elif s>target:
                    right-=1
                else:
                    return res
        return res

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。

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
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        result=[]
        self.findNsum(nums,target,4,[],result)
        return result

    def findNsum(self, nums, target, N, temp, result):
        if len(nums)<N or N<2:
            return

        if N==2:
            left,right=0,len(nums)-1
            while left<right:
                summation=nums[left]+nums[right]
                if summation==target:
                    result.append(temp+[nums[left],nums[right]])
                    left+=1
                    right-=1
                    while left<right and nums[left]==nums[left-1]:
                        left+=1
                    while right>left and nums[right]==nums[right+1]:
                        right-=1
                elif summation<target:
                    left+=1
                else:
                    right-=1
        else:
            for i in range(len(nums)-N+1):
                if target<nums[i]*N or target>nums[-1]*N:
                    break
                if i==0 or i>0 and nums[i-1]!=nums[i]:
                    self.findNsum(nums[i+1:],target-nums[i],N-1,temp+[nums[i]],result)
        return