美文网首页
【算法题】2270. 分割数组的方案数

【算法题】2270. 分割数组的方案数

作者: 程序员小2 | 来源:发表于2023-03-12 22:02 被阅读0次

题目:

给你一个下标从 0 开始长度为 n 的整数数组 nums 。
如果以下描述为真,那么 nums 在下标 i 处有一个 合法的分割 :

前 i + 1 个元素的和 大于等于 剩下的 n - i - 1 个元素的和。
下标 i 的右边 至少有一个 元素,也就是说下标 i 满足 0 <= i < n - 1 。
请你返回 nums 中的 合法分割 方案数。

示例 1:

输入:nums = [10,4,-8,7]
输出:2
解释:
总共有 3 种不同的方案可以将 nums 分割成两个非空的部分:

  • 在下标 0 处分割 nums 。那么第一部分为 [10] ,和为 10 。第二部分为 [4,-8,7] ,和为 3 。因为 10 >= 3 ,所以 i = 0 是一个合法的分割。
  • 在下标 1 处分割 nums 。那么第一部分为 [10,4] ,和为 14 。第二部分为 [-8,7] ,和为 -1 。因为 14 >= -1 ,所以 i = 1 是一个合法的分割。
  • 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ,和为 6 。第二部分为 [7] ,和为 7 。因为 6 < 7 ,所以 i = 2 不是一个合法的分割。
    所以 nums 中总共合法分割方案受为 2 。
    示例 2:

输入:nums = [2,3,1,0]
输出:2
解释:
总共有 2 种 nums 的合法分割:

  • 在下标 1 处分割 nums 。那么第一部分为 [2,3] ,和为 5 。第二部分为 [1,0] ,和为 1 。因为 5 >= 1 ,所以 i = 1 是一个合法的分割。
  • 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ,和为 6 。第二部分为 [0] ,和为 0 。因为 6 >= 0 ,所以 i = 2 是一个合法的分割。

提示:

2 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5

java代码:

class Solution {
  public int waysToSplitArray(int[] nums) {
    int n = nums.length, cnt = 0;
    long[] sum = new long[n + 1];
    for (int i = 0; i < n; i++) {
      sum[i + 1] = sum[i] + nums[i];
    }
    for (int i = 0; i < n - 1; i++) {
      if (sum[i + 1] * 2 >= sum[n]) cnt++;
    }
    return cnt;
  }
}

相关文章

  • 算法(leetode)300题之(1)两数之和

    标题:算法(leetode)300题之(1)两数之和 题目描述 方案总览 1 方案1 1)代码: 2 方案2 1)...

  • 前端算法题收集

    数组去重和排序的多种实现算法 数组扁平化的N种实现方案 阿里面试题之斐波那契数列 字节跳动经典算法题

  • LeetCode-15 三数之和

    题目:15. 三数之和 难度:中等 分类:数组 解决方案:双指针 今天我们学习第15题三数之和,这是一道中等题。像...

  • LeetCode-18 四数之和

    题目:18. 四数之和 难度:中等 分类:数组 解决方案:双指针 今天我们学习第18题四数之和,这是一道中等题。像...

  • 最简单的算法题,你会吗?

    leetcode上算法第一题,求两数之和,是最简单的算法题。 给定一个整数数组 nums 和一个目标值 targe...

  • numpy - 学习笔记

    基础 随机数 正态分布 数组连结 数组分割 计时器 数组积累 基础 nparray.ndim 数组维数 nparr...

  • 三路快排算法-求中位数问题(4)

    算法面试高频题,求前K个数,或者求中位数 三路快排算法思路 将数组分为三部分,随机选择数组中的一个数,使数组左边都...

  • three way partition

    问题描述 partition算法就是将我们的一个数组中的数分成高低两部分,返回分割点的位置。而三路划分将数组中的数...

  • 实现整数的数字翻转

    题目:(力扣第7题) 思路,整数转换为字符串再转化为char数组方案一:逆序输出(暴力破解)数据结构:字符数组算法...

  • LeetCode-79 单词搜索

    题目:79. 单词搜索 难度:中等 分类:数组 解决方案:DFS、回溯算法 今天我们学习第79题单词搜索,这个题目...

网友评论

      本文标题:【算法题】2270. 分割数组的方案数

      本文链接:https://www.haomeiwen.com/subject/gbpqrdtx.html