LeetCode 6254. 划分技能点相等的团队

6254. 划分技能点相等的团队

【哈希表】先求个sum，然后看能不能划分为n / 2份，将划分后的大小设置为target，枚举skill，对于枚举的每一个x，在哈希表中寻找是否出现target - x，并且他的个数 > 0才行，如果出现就把哈希表中的这个值的记录 -1，否则就将他加入哈希表。

class Solution {
public:
 
    // 哈希表
    // 4:12 4
 
    long long dividePlayers(vector<int>& skill) {
        unordered_map<int, int> hash;
        int sum = 0, n = skill.size() / 2;
        for (int s: skill) sum += s;
        if (sum % n) return -1;
        int tar = sum / n;
        long long ans = 0;
        for (int s: skill) {
            int t = tar - s;
            if (hash[t]) {
                ans += s * t;
                hash[t] --;
            } else {
                hash[s] ++;
            }
        }
        for (auto &[k, v]: hash) {
            if (v) return -1;
        }
        return ans;
    }
};

class Solution {
    public long dividePlayers(int[] skill) {
        int sum = 0, n = skill.length, m = n / 2;
        Map map = new HashMap();
        for (int s: skill) {
            sum += s;
        }
        if (sum % m != 0) return -1;
        int t = sum / m;
        int cnt = 0;
        long ans = 0;
        for (int s: skill) {
            int tmp = t - s;
            if (map.containsKey(tmp) && map.get(tmp) != 0) {
                cnt ++;
                ans += tmp * s;
                map.put(tmp, map.get(tmp) - 1);
            } else {
                map.put(s, map.getOrDefault(s, 0) + 1);
            }
        }
        if (cnt != m) return -1;
        return ans;
    }
}

【排序+双指针】

class Solution {
public:
 
    // 排序 + 双指针
    // 4:52
 
    long long dividePlayers(vector<int>& skill) {
        int sum = 0, n = skill.size() / 2;
        for (int s: skill) sum += s;
        if (sum % n) return -1;
        int tar = sum / n;
        sort(skill.begin(), skill.end());
        long long ans = 0;
        for (int i = 0, j = skill.size() - 1; i < j; i++, j--) {
            if (skill[i] + skill[j] != tar) return -1;
            else ans += skill[i] * skill[j];
        }
        return ans;
    }
};