0923. 3Sum With Multiplicity

题目信息

题号:

0923

难度:

Medium

主题:

数组、三元组计数、重复值

原题:

LeetCode 0923

重点:

统计的是满足 i < j < k 的下标三元组;相同数值来自不同下标时属于不同方案,结果需要取模

题目重述

给定整数数组 arr 和整数 target。请统计下标三元组 (i, j, k) 的数量,使其满足 0 <= i < j < k < arr.length,并且 arr[i] + arr[j] + arr[k] == target。

数组可以包含重复值。即使三个数值组合相同,只要使用的下标不同,就属于不同三元组。请返回数量对 10^9 + 7 取模后的结果。

3 <= arr.length <= 3000,0 <= arr[i] <= 100,0 <= target <= 300。

自建示例

重复值产生多个下标组合:

输入:arr = [1,1,2,2,3], target = 5
输出:3
解释:数值组合 1+1+3 有 1 种下标选择;组合 1+2+2 可以任选两个 1 中的一个,有 2 种选择,总计 3。

最小长度数组没有合法三元组:

输入:arr = [0,0,0], target = 1
输出:0
解释:唯一可选的三个下标之和为 0,不等于目标 1,因此没有合法三元组。