三个数的和小于等于k
三个数的和小于等于k
echobingo
发布于 2018-04-25 17:19:48
发布于 2018-04-25 17:19:48
给一个数组以及一个数K， 从这个数组里面选择三个数，使得三个数的和小于等于K， 有多少种选择的方法？（不包括重复的情况）
Example：
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 = [1,2,2,2,3,3,4,5] ，外循环先取第一个数 1，将问题转化为在 [2,2,2,3,3,4,5] 中找到下于等于 k-1 = 6 的两个数。
- 内循环高低指针 low -> 2，high -> 5，然后 high 后移，high -> 4，这个时候，由第一个 2 作为第二个数，与其组合有的 [2,2] [2,2] [2,3] [2,3] [2,4]，但是要去除重复的 [2,2] 和 [2,3]。
- 这里我们开辟一个 O(n) 的空间 dup[0..n-1]，dup[i] 记录第 i 个元素之前共出现了多少次重复的元素。比如 nums = [1,2,2,2,3,3,4,5] ，我们可以得到 dup = [0,0,1,2,2,3,3,3]。我们记录了 low 和 high 之间有5种组合（high - low），还要去除 low->2、high -> 4 之间的位置出现的重复次数 3（dup[6] - dup[0] = 3）。但是这时相当于我们多去除了一种组合，即我们把第一个 [2,2] 也给去除了，所以要多补充1。但是，也存在这样的情况，比如 k = 10，low -> 4, high - > 5，这时我们用 （high - low）再减去 low、high 之间重复的元素 0 （dup[7] - dup[6] = 0），结果为1，就是 [4,5] 这种情况，但是这时不需要再加1，因为 4 和 5 两个数字不相同，所以不存在多除去 1 种组合的情况。因此，在这里，我们要注意分两个情况，一种是
nums[low] == nums[low+1]，要多补充1，否则不用补充。 - 将 low 移动到下一个不重复的数字处 low -> 3，可以找到 [3,3]，然后low、high相遇，内循环遍历结束。
- 外循环接着重复取数 nums[2...n-2]（但是要跳过相同的数字，比如该次取得数为 2，下一次外循环要跳过后面所有相同的 2，直接到下一个不同的数字 3 那里），然后内循环进行指针移动操作，可以找到所有不重复的组合数。
空间复杂度：O(n)
Python 实现：
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本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录