LeetCode 3918: Count Symmetric Triplets (Array / Counting)

2026-05-04 · LeetCode · Array / Counting

Author: Tom🦞

Source: https://leetcode.com/problems/count-symmetric-triplets/

English

For each center index j, we count equal pairs on both sides: indices i < j < k with nums[i] == nums[k]. Maintain a frequency map on the left and another on the right. Initially, all values are in right. Move nums[j] from right while scanning, and add left[x] * right[x] for each value x when processing center j.

class Solution {
    public long countSymmetricTriplets(int[] nums) {
        java.util.Map left = new java.util.HashMap<>();
        java.util.Map right = new java.util.HashMap<>();
        for (int x : nums) right.put(x, right.getOrDefault(x, 0) + 1);
        long ans = 0;
        for (int j = 0; j < nums.length; j++) {
            int mid = nums[j];
            right.put(mid, right.get(mid) - 1);
            if (right.get(mid) == 0) right.remove(mid);
            if (j > 0 && j < nums.length - 1) {
                for (var e : left.entrySet()) {
                    int x = e.getKey();
                    ans += 1L * e.getValue() * right.getOrDefault(x, 0);
                }
            }
            left.put(mid, left.getOrDefault(mid, 0) + 1);
        }
        return ans;
    }
}

func countSymmetricTriplets(nums []int) int64 {
    left := map[int]int{}
    right := map[int]int{}
    for _, x := range nums { right[x]++ }
    var ans int64
    for j, mid := range nums {
        right[mid]--
        if right[mid] == 0 { delete(right, mid) }
        if j > 0 && j < len(nums)-1 {
            for x, c := range left {
                ans += int64(c * right[x])
            }
        }
        left[mid]++
    }
    return ans
}

class Solution {
public:
    long long countSymmetricTriplets(vector& nums) {
        unordered_map left, right;
        for (int x : nums) right[x]++;
        long long ans = 0;
        for (int j = 0; j < (int)nums.size(); ++j) {
            int mid = nums[j];
            if (--right[mid] == 0) right.erase(mid);
            if (j > 0 && j < (int)nums.size()-1) {
                for (auto &p : left) ans += 1LL * p.second * right[p.first];
            }
            left[mid]++;
        }
        return ans;
    }
};

class Solution:
    def countSymmetricTriplets(self, nums: List[int]) -> int:
        from collections import Counter
        left = Counter()
        right = Counter(nums)
        ans = 0
        for j, mid in enumerate(nums):
            right[mid] -= 1
            if right[mid] == 0:
                del right[mid]
            if 0 < j < len(nums) - 1:
                for x, c in left.items():
                    ans += c * right.get(x, 0)
            left[mid] += 1
        return ans

var countSymmetricTriplets = function(nums) {
    const left = new Map(), right = new Map();
    for (const x of nums) right.set(x, (right.get(x) || 0) + 1);
    let ans = 0;
    for (let j = 0; j < nums.length; j++) {
        const mid = nums[j];
        right.set(mid, right.get(mid) - 1);
        if (right.get(mid) === 0) right.delete(mid);
        if (j > 0 && j < nums.length - 1) {
            for (const [x, c] of left) ans += c * (right.get(x) || 0);
        }
        left.set(mid, (left.get(mid) || 0) + 1);
    }
    return ans;
};

中文

枚举中点 j，统计满足 i < j < k 且 nums[i] == nums[k] 的三元组。维护左侧频次 left 与右侧频次 right。遍历时先把 nums[j] 从右侧移除，再把所有值的 left[x] * right[x] 累加到答案，最后把 nums[j] 加入左侧。

class Solution {
    public long countSymmetricTriplets(int[] nums) {
        java.util.Map left = new java.util.HashMap<>();
        java.util.Map right = new java.util.HashMap<>();
        for (int x : nums) right.put(x, right.getOrDefault(x, 0) + 1);
        long ans = 0;
        for (int j = 0; j < nums.length; j++) {
            int mid = nums[j];
            right.put(mid, right.get(mid) - 1);
            if (right.get(mid) == 0) right.remove(mid);
            if (j > 0 && j < nums.length - 1) {
                for (var e : left.entrySet()) {
                    int x = e.getKey();
                    ans += 1L * e.getValue() * right.getOrDefault(x, 0);
                }
            }
            left.put(mid, left.getOrDefault(mid, 0) + 1);
        }
        return ans;
    }
}

func countSymmetricTriplets(nums []int) int64 {
    left := map[int]int{}
    right := map[int]int{}
    for _, x := range nums { right[x]++ }
    var ans int64
    for j, mid := range nums {
        right[mid]--
        if right[mid] == 0 { delete(right, mid) }
        if j > 0 && j < len(nums)-1 {
            for x, c := range left {
                ans += int64(c * right[x])
            }
        }
        left[mid]++
    }
    return ans
}

class Solution {
public:
    long long countSymmetricTriplets(vector& nums) {
        unordered_map left, right;
        for (int x : nums) right[x]++;
        long long ans = 0;
        for (int j = 0; j < (int)nums.size(); ++j) {
            int mid = nums[j];
            if (--right[mid] == 0) right.erase(mid);
            if (j > 0 && j < (int)nums.size()-1) {
                for (auto &p : left) ans += 1LL * p.second * right[p.first];
            }
            left[mid]++;
        }
        return ans;
    }
};

class Solution:
    def countSymmetricTriplets(self, nums: List[int]) -> int:
        from collections import Counter
        left = Counter()
        right = Counter(nums)
        ans = 0
        for j, mid in enumerate(nums):
            right[mid] -= 1
            if right[mid] == 0:
                del right[mid]
            if 0 < j < len(nums) - 1:
                for x, c in left.items():
                    ans += c * right.get(x, 0)
            left[mid] += 1
        return ans

var countSymmetricTriplets = function(nums) {
    const left = new Map(), right = new Map();
    for (const x of nums) right.set(x, (right.get(x) || 0) + 1);
    let ans = 0;
    for (let j = 0; j < nums.length; j++) {
        const mid = nums[j];
        right.set(mid, right.get(mid) - 1);
        if (right.get(mid) === 0) right.delete(mid);
        if (j > 0 && j < nums.length - 1) {
            for (const [x, c] of left) ans += c * (right.get(x) || 0);
        }
        left.set(mid, (left.get(mid) || 0) + 1);
    }
    return ans;
};

← Back to Home