给一个数组以及一个数K, 从这个数组里面选择三个数,使得三个数的和小于等于K, 有多少种选择的方法?(不包括重复的情况)
Input:
nums = [3,2,5,2,1,4,2,3]
k = 7
Output:
6 # [1,2,4], [1,2,3], [1,2,2], [1,3,3], [2,2,2], [2,2,3]
这个题是“三个数的和等于K”的变形,主要难点在于去重。首先,还是先列表从小到大排序,然后外循环遍历 nums[0...n-2],将三个数问题转化为两个数问题。
在两个数的和小于等于K的问题中,同样设置高低指针,然后判断低指针指向的元素与高指针指向的元素之和是否小于等于K,如果不是,高指针向左移动;否则,数出高低指针中间有多少个不重复的组合,然后低指针向右移动。当高低指针相遇,内循环结束,也需要 O(n) 的时间。
总共需要的时间复杂度为 O(n^2)。
前面提到,难点在于去除重复的组合数。这里以上述例子来分析:
nums[low] == nums[low+1]
,要多补充1,否则不用补充。 空间复杂度:O(n)
class Solution:
"""
@param nums: 数组
@param k: 3个数的和小于等于k
@return: 3个数小于等于k的个数(相同的组合次数只记为一次)
"""
def threeLtEqK(self, nums, k):
if len(nums) <= 2:
return 0
nums.sort() # 排序
dup = self.statisDupliNums(nums) # 统计重复的元素
count = i = 0
while i < len(nums) - 2:
count += self.twoLtEqK(nums[i+1:], i+1, k-nums[i], dup) # 将3个数问题转化为两个数问题
while nums[i] == nums[i+1]: # 去除重复走过的元素
i += 1
i += 1
return count
# 统计排好序的列表中第i个元素前累积出现的重复的元素次数
# 如 [1,2,2,2,3,3],返回 [0,0,1,2,2,3]
def statisDupliNums(self, nums):
dup = [0] * len(nums)
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
dup[i] = dup[i-1] + 1
else:
dup[i] = dup[i-1]
return dup
# 转化为两个数的和小于等于k的问题
def twoLtEqK(self, nums, nextIndix, k, dup):
count = 0
low, high = 0, len(nums) - 1
while low < high:
if nums[low] + nums[high] <= k:
# 去重重复组合数后的数量
if nums[low] == nums[low+1]: # 这种情况下多去除了一次,所以补1
noDupNum = (high - low) - (dup[high+nextIndix] - dup[low+nextIndix]) + 1
else:
noDupNum = (high - low) - (dup[high+nextIndix] - dup[low+nextIndix])
count += noDupNum
while nums[low] == nums[low+1]:
low += 1
low += 1 # 从下一个非重复的元素开始
else:
high -= 1
return count
a = [3,2,5,2,1,4,2,3]
print(Solution().threeLtEqK(a,7)) # 6
print(Solution().threeLtEqK(a,10)) # 16