2022-1-30 Leetcode 5981.分组得分最高的所有下标

前两版的方法都超时了，
第三版方法的核心是：最初的得分为整个数组的和，在从左向右的扫描的过程中，如果遇到 0 就加一分（说明右边的 1 的个数之和没有变，左边因为多了一个 0 而加上一分），如果遇到 1 就扣一分（说明右边 1 的个数之和少了一个，扣一分；左边的 0 个数之和没有变）。

第一版：

class Solution {
public:
    vector maxScoreIndices(vector& nums) {
        map myMap;
        for(int i = 0;i <= nums.size();i++){
            myMap[i] += accumulate(nums.begin()+i,nums.end(),0);
            myMap[i] += i-accumulate(nums.begin(),nums.begin()+i,0);
        }
        int score = 0;
        vector ret;
        for(auto it = myMap.begin();it != myMap.end();it++){
            if(it->second == score){
                ret.push_back(it->first);
            }
            else if(it->second > score){
                ret.clear();
                ret.push_back(it->first);
                score = it->second;
            }
        }
        return ret;
    }
};

第二版

class Solution {
public:
    vector maxScoreIndices(vector& nums) {
        vector ret;
        int eachScore = 0;
        int maxScore = 0;
        for(int i = 0;i <= nums.size();i++){
            
            eachScore += count(nums.begin(),nums.begin()+i,0);
            eachScore += count(nums.begin()+i,nums.end(),1);
            if(eachScore > maxScore){
                ret.clear();
                ret.push_back(i);
                maxScore = eachScore;
            }
            else if(eachScore == maxScore){
                ret.push_back(i);
            }
        }
        return ret;
    }
};

第三版

class Solution {
public:
    vector maxScoreIndices(vector& nums) {
        vector ret;
        int totalScore = accumulate(nums.begin(),nums.end(),0);
        int maxScore = 0;
        
        for(int i = 0;i <= nums.size();i++){
            if(maxScore == totalScore){
                ret.push_back(i);
            }
            else if(maxScore < totalScore){
                ret.clear();
                maxScore = totalScore;
                ret.push_back(i);
            }
            if(i < nums.size()){
                if(nums[i])
                    --totalScore;
                else ++totalScore;
            }
        }
        return ret;
    }
};