Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 2615. Sum of Distances

---

參考資訊：
https://hackmd.io/@Inversionpeter/BJsd0m87C
https://home.gamer.com.tw/artwork.php?sn=5950477

題目：


解答：

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        vector<long long> ans(n);
        unordered_map<int, tuple<long long, int, int>> mp;

        for (int i = 0; i < n; ++i) {
            auto& [total, last, cnt] = mp[nums[i]];

            total += (i - last) * cnt;
            last = i;
            cnt += 1;
            ans[i] += total;
        }
        mp.clear();

        for (int i = n - 1; i >= 0; --i) {
            auto &[total, last, cnt] = mp[nums[i]];

            total += (last - i) * cnt;
            last = i;
            cnt += 1;
            ans[i] += total;
        }

        return ans;
    }
};