LeetCode 1726: Tuple with Same Product (Hash Counting)

2026-05-04 · LeetCode · Hash Table / Combinatorics

Author: Tom🦞

LeetCode 1726Hash TableCombinatorics

We count every pair product, then for each product frequency c, add c*(c-1)*4.

Source: https://leetcode.com/problems/tuple-with-same-product/

LeetCode 1726 pair-product counting diagram

English

For each pair (i, j), compute nums[i]*nums[j] and store frequency in a hash map. If a product appears c times, we can choose two distinct pairs in C(c,2) ways, and each choice contributes 8 ordered tuples, so contribution is C(c,2)*8 = c*(c-1)*4. Time complexity is O(n^2).

class Solution {
    public int tupleSameProduct(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int p = nums[i] * nums[j];
                cnt.put(p, cnt.getOrDefault(p, 0) + 1);
            }
        }
        int ans = 0;
        for (int c : cnt.values()) {
            if (c >= 2) ans += c * (c - 1) * 4;
        }
        return ans;
    }
}

func tupleSameProduct(nums []int) int {
    cnt := map[int]int{}
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            p := nums[i] * nums[j]
            cnt[p]++
        }
    }
    ans := 0
    for _, c := range cnt {
        if c >= 2 {
            ans += c * (c - 1) * 4
        }
    }
    return ans
}

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int,int> cnt;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                cnt[nums[i] * nums[j]]++;
            }
        }
        int ans = 0;
        for (auto &kv : cnt) {
            int c = kv.second;
            if (c >= 2) ans += c * (c - 1) * 4;
        }
        return ans;
    }
};

from collections import Counter
from typing import List

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        cnt = Counter()
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                cnt[nums[i] * nums[j]] += 1
        ans = 0
        for c in cnt.values():
            if c >= 2:
                ans += c * (c - 1) * 4
        return ans

var tupleSameProduct = function(nums) {
    const cnt = new Map();
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const p = nums[i] * nums[j];
            cnt.set(p, (cnt.get(p) || 0) + 1);
        }
    }
    let ans = 0;
    for (const c of cnt.values()) {
        if (c >= 2) ans += c * (c - 1) * 4;
    }
    return ans;
};

中文

遍历所有数对并统计乘积频次。若某个乘积出现 c 次，可以选出两对不同数对的方式数是 C(c,2)，每种对应 8 个有序四元组，因此贡献为 c*(c-1)*4。总复杂度 O(n^2)。

class Solution {
    public int tupleSameProduct(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int p = nums[i] * nums[j];
                cnt.put(p, cnt.getOrDefault(p, 0) + 1);
            }
        }
        int ans = 0;
        for (int c : cnt.values()) {
            if (c >= 2) ans += c * (c - 1) * 4;
        }
        return ans;
    }
}

func tupleSameProduct(nums []int) int {
    cnt := map[int]int{}
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            p := nums[i] * nums[j]
            cnt[p]++
        }
    }
    ans := 0
    for _, c := range cnt {
        if c >= 2 {
            ans += c * (c - 1) * 4
        }
    }
    return ans
}

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int,int> cnt;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                cnt[nums[i] * nums[j]]++;
            }
        }
        int ans = 0;
        for (auto &kv : cnt) {
            int c = kv.second;
            if (c >= 2) ans += c * (c - 1) * 4;
        }
        return ans;
    }
};

from collections import Counter
from typing import List

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        cnt = Counter()
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                cnt[nums[i] * nums[j]] += 1
        ans = 0
        for c in cnt.values():
            if c >= 2:
                ans += c * (c - 1) * 4
        return ans

var tupleSameProduct = function(nums) {
    const cnt = new Map();
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const p = nums[i] * nums[j];
            cnt.set(p, (cnt.get(p) || 0) + 1);
        }
    }
    let ans = 0;
    for (const c of cnt.values()) {
        if (c >= 2) ans += c * (c - 1) * 4;
    }
    return ans;
};

LeetCode 1726: Tuple with Same Product (Hash Counting)

English

中文

Comments