K 数之和总结

[TOC]

1. Two Sum

题目：https://leetcode-cn.com/problems/two-sum/description/

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Solution 1

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """       
        n = len(nums)
        for x in range(n):
            b = target-nums[x]
            if b in nums:
                y = nums.index(b)
                if y!=x:
                    return x,y

分析：时间复杂度：O(n2)，空间复杂度：O(1) （补充：python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n) 也就是 if b in nums 时间复杂度是O(n)）。

Solution 2

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """           
        n = len(nums)
        # Create a empty dict
        d = {}
        for x in range(n):
            a = target-nums[x]
            if nums[x] in d:
                return d[nums[x]],x
            else:
                d[a] = x

分析：时间复杂度：O(1) 、空间复杂度O(n) （补充：dict对象的存储结构采用的是散列表(hash表)，其在最优情况下查询复杂度为O(1)）。

2. Three Sum

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路:
首先从大的方面来看，排序之后比较容易做到去重，相同元素直接选取代表即可。

拍完序之后，以下标i从左往右遍历作为主循环，找到剩下两个加起来和为-nums[i]的两个元素。

这样的两个元素一定出现在nums[i]后面，这个限制非常关键。因为主循环是从左往右遍历，如果不限制只在当前元素后面找，则会重复答案。

加上这个限制，如果当前元素大于0，则表示后面的所有元素都大于0，三个数相加之和不可能为0.

这里有两次去重的概念，首先是在外层，如果nums[i]和上一个元素nums[i-1]相同，则直接跳过，因为相同值已经考虑过了。

另一个是在三数之和为0时，还要其他的解，这里也考虑一次去重即可。

Solution 1

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3 or nums == None:
            return None
        # 本题需要去重
        nums.sort() # 原地排序
        res = []
        # 三指针： nums[j] + nums[k] == -nums[i]
        for i in range(len(nums)):
            # 排序之后，nums[i]大于0则不可能从后面找到解
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                _sum = nums[i] + nums[j] + nums[k]
                if _sum == 0:
                    temp = [nums[i], nums[j], nums[k]]
                    res.append(temp)
                    while j < k and nums[j] == nums[j + 1]:
                        j += 1
                    while j < k and nums[k] == nums[k-1]:
                        k -= 1
                    j += 1
                    k -= 1
        
                elif _sum > 0:
                    k -= 1
                elif _sum < 0:
                    j += 1
        return res

Solution 2

class Solution(object):
    def threeSum(self, nums):
        
        '''这题跟11盛水一样，用双指针法'''
        
        nums=sorted(nums,reverse=False) #从小到大sorted临时排序  sort永久性排序[-4 -1…2]
        new_list = []
        for key,value in enumerate(nums):   #运用双指针时这种方法学一下
            j,k = key + 1, len(nums) - 1    #从下一位和最后一位向中间遍历
            while j < k:                    #两个指针向中间移动
                if nums[j] + nums[k] + value == 0:
                    if [nums[j],nums[k],value] not in new_list:   #去重
                        new_list.append([nums[j],nums[k],value])
                    while j < k and nums[j] == nums[j+1]:    #去重
                        j += 1
                    while j < k and nums[k] == nums[k-1]:    #去重
                        k -= 1
                    j += 1
                    k -= 1
                # 大于 0, 右指针向中间移动
                elif nums[j] + nums[k] + value > 0:
                    k -= 1
                # 小于 0,左指针向中间移动
                else:
                    j += 1
        return new_list

Solution 3

class Solution:#递归解法
    def threeSum(self, nums):#nums = [-1, 0, 1, 2, -1, -4]
        def findNsum(nums, target, N, result, results):#result某一次结果results最终结果
            if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:#
                return  #某些情况：不符合N数之和；N=1；
                        #找不到的两种情况：target<N个最小数；target>N个最大数
            if N == 2: # N数之和都要递归到两数之和解决
                l,r = 0,len(nums)-1#注意这里都是排过序的，，双指针
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l-1]:#相同的数跳过
                            l += 1
                    elif s < target:
                        l += 1 #比target小左指针加1
                    else:
                        r -= 1 #比target大左指针加1
            else: # 3数，4数，N数之和……
                for i in range(len(nums)-N+1): #对于剩下的数
                    if i == 0 or (i > 0 and nums[i-1] != nums[i]): #
                        findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results) #
 
        results = []
        findNsum(sorted(nums), 0, 3, [], results)
        return results

3. Four Sum

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

注意：

答案中不可以包含重复的四元组。

示例：

给定数组nums = [1, 0, -1, 0, -2, 2]，和target = 0。

满足要求的四元组集合为：

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路:
本题是三数之和的延续。也包含去重，所以，排序是基本操作。

三数之和是固定一个数，然后在后面用双指针查找，四数之和是固定两个数，然后用双指针在后面查找。

Solution 1

class Solution:#递归解法
    def fourSum(self, nums, target):
        def findNsum(nums, target, N, result, results):
            if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination
                return
            if N == 2: # two pointers solve sorted 2-sum problem
                l,r = 0,len(nums)-1
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else: # recursively reduce N
                for i in range(len(nums)-N+1):
                    if i == 0 or (i > 0 and nums[i-1] != nums[i]):
                        findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
 
        results = []
        findNsum(sorted(nums), target, 4, [], results)
        return results

Solution 2:

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if len(nums) < 4 or nums == None:
            return None
        nums.sort()
        res = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            newTarget = target - nums[i]
            
            for j in range(i + 1, len(nums)):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                newTarget2 = newTarget - nums[j]
                
                m = j + 1
                n = len(nums) - 1
                
                while m < n:
                    if nums[m] + nums[n] == newTarget2:
                        temp = [nums[i], nums[j], nums[m], nums[n]]
                        res.append(temp)
                        while m < n and nums[m] == nums[m+1]:
                            m += 1
                        while m < n and nums[n] == nums[n-1]:
                            n -= 1
                        m += 1
                        n -= 1
                    elif nums[m] + nums[n] > newTarget2:
                        n -= 1
                    elif nums[m] + nums[n] < newTarget2:
                        m += 1
        return res

4. K Sum

Problem:

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example:

Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

Note:

这道题和Distinct Subsequence很像。
使用三维动规数组dp[i][j][t]，表示从0遍历到A[i]后找到的j个元素之和为t的情况的总数。最后返回从整个A数组找到的k个元素之和为target的情况总数即可。操作如下：
首先，若第i个元素，也就是A[i-1]，大于t，那么“从前i个元素中取j个元素令j个元素之和为t的所有情况”和第i个元素无关。也就是说dp[i][j][t] = dp[i-1][j][t]。而如果最后一个元素A[i-1] <= t，那么这个元素一定能带来一些不同的“从前i个元素中取j个元素令j个元素之和为t的情况”，但是，还要加上完全不考虑这个元素A[i-1]时的解的集合，也就是dp[i-1][j-1][t-A[i-1]]。因为，加上这个元素之后的dp[i][j-1][t-A[i-1]]不会影响已经遍历过的dp[i-1][j-1][t-A[i-1]]。

Solution

public class Solution {
    public int kSum(int A[], int k, int target) {
        int[][][] dp = new int[A.length+1][k+1][target+1];
        for (int i = 0; i <= A.length; i++) dp[i][0][0] = 1;
        //Super DP
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    dp[i][j][t] = dp[i-1][j][t];
                    if (A[i-1] <= t) dp[i][j][t] += dp[i-1][j-1][t-A[i-1]];
                }
            }
        }
        return dp[A.length][k][target];
    }
}
Last modification：September 24, 2019
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏