[数据结构与算法]【力扣题解】2155. 分组得分最高的所有下标

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

一、题目

1、题目描述

给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。

• numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。
• 如果 i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。
• 如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。
  
  下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
  
  返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。

2、基础框架

• Java版本框架代码如下：

class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
    
    }
}

3、原题链接

2155. 分组得分最高的所有下标

二、解题报告

1、思路分析

???????(1)先算出数组的前缀和，那么在nums数组中，当nums[i]不为0时，从0~i的零的个数即为这段数组的长度减去nums[i-1]。从i~n的1的个数为nums[n - 1] - nums[i - 1]。所以循环计算，找出最大值返回即可。

2、代码详解

class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        List<Integer> res = new ArrayList();
        int n = nums.length;
        for(int i = 1;i < nums.length;i++) {
            nums[i] += nums[i - 1];
        }
        int max = nums[n - 1];
        res.add(0);
        for(int i = 1;i <= n;i++) {
            int left = 0;
            int right = 0;
            if(nums[i - 1] == 0) {
                left = i;
            }else {
                left = i - nums[i - 1];
            }
            right = nums[n - 1] - nums[i - 1];
            int sum = left + right;
            if(max < sum) {
                res.clear();
                res.add(i);
                max = sum;
            }else if(max == sum) {
                res.add(i);
            }
        }
        
        return res;
    }
}

三、本题知识

前缀和