三个数的和小于等于k

给一个数组以及一个数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)。

前面提到,难点在于去除重复的组合数。这里以上述例子来分析:

  1. 得到排序后的 nums = [1,2,2,2,3,3,4,5] ,外循环先取第一个数 1,将问题转化为在 [2,2,2,3,3,4,5] 中找到下于等于 k-1 = 6 的两个数。
  2. 内循环高低指针 low -> 2,high -> 5,然后 high 后移,high -> 4,这个时候,由第一个 2 作为第二个数,与其组合有的 [2,2] [2,2] [2,3] [2,3] [2,4],但是要去除重复的 [2,2] 和 [2,3]。
  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,否则不用补充。
  4. 将 low 移动到下一个不重复的数字处 low -> 3,可以找到 [3,3],然后low、high相遇,内循环遍历结束。
  5. 外循环接着重复取数 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程之旅

Swift学习笔记(一)

891
来自专栏C++

python笔记:#010#运算符

1311
来自专栏流媒体

C++多态

当类存在虚函数时,编译器会为该类维护一个表,这个表就是虚函数表(vtbl),里面存放了该类虚函数的函数指针。在构造类的时候增加一个虚表指针(vptr)指向对应的...

1163
来自专栏WindCoder

《简明 Python 教程》学习笔记-运算符与表达式

又两天没更新了,暂且同步两篇之前的笔记。运算符与表达式这一块感觉主要就是运算符与它们的用法以及优先级了。

1062
来自专栏Python小屋

详解Python函数式编程之map、reduce、filter

map()、reduce()、filter()是Python中很常用的几个函数,也是Python支持函数式编程的重要体现。不过,在Python 3.x中,red...

3706
来自专栏我和PYTHON有个约会

25. 企业级开发基础6:面向对象特征(继承)

继承是让我们抽象的对象之间存在一定的所属关系 在继承关系中,我们一定要明确会出现这样的一种关系~父类、子类,子类继承自父类,可以继承父类中的公开的属性和方法(...

731
来自专栏机器学习实践二三事

python基础----函数作为返回值

从一个例子讲起 高阶函数除了可以接受函数作为参数外,还可以把函数作为结果值返回。 还是考虑这个问题:对可变参数进行求和 看了上一讲的已经知道,可以使用’*’...

2705
来自专栏lonelydawn的前端猿区

js高精度浮点数运算

贴代码:  // 自定义高精度浮点数运算 // 对象格式写法 var float_calculator={ /** * 1.记录两个运算数小数点后的位数 ...

52510
来自专栏北京马哥教育

正则表达式基本语法

\将下一字符标记为特殊字符、文本、反向引用或八进制转义符。例如,“n”匹配字符“n”。“\n”匹配换行符。序列“\\”匹配“\”,“\(”匹配“(”。^匹...

3627
来自专栏ACM算法日常

leetcode 41| 缺失的第一个正数

难点分析:是不是和笔者一样,刚看完一遍题目都不知道它在问什么~经过多次揣摩之后,笔者终于懂了这道题目到底在问什么。其实它就是给定一个数组,然后看看数组中是否包含...

1892

扫码关注云+社区

领取腾讯云代金券