原文链接: https://leetcode-cn.com/problems/count-special-quadruplets

英文原文

Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:

• nums[a] + nums[b] + nums[c] == nums[d], and
• a < b < c < d

 

Example 1:

Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.

Example 2:

Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].

Example 3:

Input: nums = [1,1,1,3,5]
Output: 4
Explanation: The 4 quadruplets that satisfy the requirement are:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

 

Constraints:

• 4 <= nums.length <= 50
• 1 <= nums[i] <= 100

中文题目

给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：

• nums[a] + nums[b] + nums[c] == nums[d] ，且
• a < b < c < d

 

示例 1：

输入：nums = [1,2,3,6]
输出：1
解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。

示例 2：

输入：nums = [3,3,6,4,5]
输出：0
解释：[3,3,6,4,5] 中不存在满足要求的四元组。

示例 3：

输入：nums = [1,1,1,3,5]
输出：4
解释：满足要求的 4 个四元组如下：
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

 

提示：

• 4 <= nums.length <= 50
• 1 <= nums[i] <= 100

通过代码

高赞题解

方法一：正向遍历，哈希保存每个数值的所有下标，然后二分查找满足条件的下标数，O(n^3*logn)。

func countQuadruplets(nums []int) int {
    cnt := 0
    n := len(nums)
    m := make(map[int][]int, n)
    for i, num := range nums { m[num] = append(m[num], i) }
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            for k := j+1; k < n; k++ {
                s := m[nums[i]+nums[j]+nums[k]]
                cnt += len(s)-sort.SearchInts(s, k+1)
            }
        }
    }
    return cnt
}

方法二：反向遍历，O(n^3)。

func countQuadruplets(nums []int) int {
    cnt := 0
    n := len(nums)
    m := make(map[int]int, n)
    for i := n-1; i >= 0; i-- {
        for j := i-1; j >= 0; j-- {
            for k := j-1; k >= 0; k-- {
                sum := nums[i]+nums[j]+nums[k]
                cnt += m[sum]
            }
        }
        m[nums[i]]++
    }
    return cnt
}

统计信息

通过次数	提交次数	AC比率
6156	10947	56.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言