美文网首页
923. 三数之和的多种可能(Python)

923. 三数之和的多种可能(Python)

作者: 玖月晴 | 来源:发表于2021-03-23 10:51 被阅读0次

难度:★★★☆☆
类型:数组
方法:指针

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个整数数组 A,以及一个整数 target 作为目标值,返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。

由于结果会非常大,请返回 结果除以 10^9 + 7 的余数。

示例 1:

输入:A = [1,1,2,2,3,3,4,4,5,5], target = 8
输出:20
解释:
按值枚举(A[i],A[j],A[k]):
(1, 2, 5) 出现 8 次;
(1, 3, 4) 出现 8 次;
(2, 2, 4) 出现 2 次;
(2, 3, 3) 出现 2 次。

示例 2:

输入:A = [1,1,2,2,2,2], target = 5
输出:12
解释:
A[i] = 1,A[j] = A[k] = 2 出现 12 次:
我们从 [1,1] 中选择一个 1,有 2 种情况,
从 [2,2,2,2] 中选出两个 2,有 6 种情况。

提示:

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

解答

还记得这道题的简化版本吗?我们来计算一下两数之和的多种可能性。

如果列表中的数字都是不同的,那么我们可以很方便的使用双指针法来解决,注意一下排序的重要性:

class Solution:
    def twoSumMulti(self, A, target):
        A.sort()
        left, right = 0, len(A) - 1
        cur_ans = 0

        while left < right:
            if A[left] + A[right] < target:
                left += 1
            elif A[left] + A[right] > target:
                right -= 1
            else:
                cur_ans += 1
        return cur_ans

问题就出在重复元素上面。我们在循环中,遇到左右指针对应元素之和等于目标值的情况,不能仅仅将可能性加一,而有必要考虑一下左右指针对应元素可能重复多次的情况。在这种情况下:

如果左右指针对应元素不一样,这就好办了,统计一下各自出现的次数,排列一下,也就是次数相乘即可。

但是如果左右指针对应元素一致,这就不是排列的问题,而是组合的问题,例如从n个a中选出两个组成2a,有多少种方法,不过数学知识告诉我们,答案是n*(n-1)//2。

写成代码,就是下面,读者可以自行比较一下与上面的区别。

class Solution:
    def twoSumMulti(self, A, target):
        A.sort()
        left, right = 0, len(A) - 1
        cur_ans = 0

        while left < right:

            if A[left] + A[right] < target:
                left += 1
            elif A[left] + A[right] > target:
                right -= 1
            else:
                if A[left] != A[right]:
                    num_left = num_right = 1
                    while A[left] == A[left + 1]:
                        num_left += 1
                        left += 1
                    while A[right] == A[right - 1]:
                        num_right += 1
                        right -= 1
                    cur_ans += num_left * num_right
                    left += 1
                    right -= 1
                else:
                    cur_ans += (right - left + 1) * (right - left) // 2
                    break
        return cur_ans

解决了两数之和的问题,三数之和就算解决了,因为我们只需要多一层循环的嵌套即可,方便的将三数问题降维成两数问题。取出一个数,求剩余数组的两数之和可能性。

class Solution:

    def threeSumMulti(self, A, target):
        ans = 0
        A.sort()
        for i, ai in enumerate(A):
            ans += self.twoSumMulti(A[i+1:], target - ai)
        return ans % (10**9 + 7)

    def twoSumMulti(self, A, target):
        # A.sort()
        left, right = 0, len(A) - 1
        cur_ans = 0

        while left < right:

            if A[left] + A[right] < target:
                left += 1
            elif A[left] + A[right] > target:
                right -= 1
            else:
                if A[left] != A[right]:
                    num_left = num_right = 1
                    while A[left] == A[left + 1]:
                        num_left += 1
                        left += 1
                    while A[right] == A[right - 1]:
                        num_right += 1
                        right -= 1
                    cur_ans += num_left * num_right
                    left += 1
                    right -= 1
                else:
                    cur_ans += (right - left + 1) * (right - left) // 2
                    break
        return cur_ans

如有疑问或建议,欢迎评论区留言~

有关更多力扣中等题的python解决方案,请移步力扣中等题解析

相关文章

  • 923. 三数之和的多种可能(Python)

    难度:★★★☆☆类型:数组方法:指针 题目 力扣链接请移步本题传送门[https://leetcode-cn.co...

  • 2020-05-04

    最长连续序列 3SUM 923. 三数之和的多种可能 300. 最长上升子序列 333. 最大 BST 子树 33...

  • algrithrom

    求和问题,双指针解决 done 两数之和 三数之和 最接近三数之和 四数之和 链表反转问题 done 链表反转 链...

  • LeetCode-923-三数之和的多种可能性

    LeetCode-923-三数之和的多种可能性 题目 给定一个整数数组 A,以及一个整数 target 作为目标值...

  • task

    task1.python实现三数之和,(正整数) class threesum: def threeSum(s...

  • Leetcode923:三数之和的多种可能性

    【思路】先用数组统计各个数字出现的次数再遍历所有可能的 i j 此时 k会自动出现i <= j <= k 且 k...

  • leetcode三数之和(python)

    开始学习算法,到leetcode上找题目练手,第一题就是两数之和,难度标注为简单,想了一段时间才想出来,差点以为脑...

  • Python小白 Leetcode刷题历程 No.16-N

    Python小白 Leetcode刷题历程 No.16-No.20 最接近的三数之和、Phone Nu...

  • LeetCode 第18题:四数之和

    1、前言 2、思路 采用三数之和的思路,原本三数之和可以分解为:数组中的一个数 + 此数右边的数求两数之和,那么四...

  • 两数之和&三数之和&四数之和&K数之和

    今天看了一道谷歌K数之和的算法题,忽然想起来之前在力扣上做过2、3、4数之和的题,觉得很有必要来整理一下。其实2、...

网友评论

      本文标题:923. 三数之和的多种可能(Python)

      本文链接:https://www.haomeiwen.com/subject/qdakqltx.html