Массивҳои тақсимот ба се қисм бо ҳалли баробари суммаи Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Microsoft
тартиботи ҳарбӣ

Мушкилоти тақсимот тартиботи ҳарбӣ Ба се қисм бо ҳалли баробари Leetcode Solution ба мо массив ё вектор медиҳад ва мепурсад, ки оё се тақсимоти пайдарпаӣ имконпазир аст. Дар ин ҷо, бо тақсимбандӣ маънои ду индекси i, j вуҷуд дорад, ки маблағи унсурҳо аз оғоз то ith ба миқдори элементҳои аз индекси i + 1 то jth баробар аст. Ва ҷамъи элементҳо аз индекси j + 1 то элементи охирин низ ба ду сегменти аввали массив баробар аст. Агар чунин ду нишондиҳанда вуҷуд дошта бошад, мо мегӯем, ки массивро бо се миқдори баробар ба се қисм тақсим кардан мумкин аст, вагарна не. Пеш аз он ки ба ҳалли масъала гузарем, биёед якчанд мисолро бубинем.

Массивҳои тақсимот ба се қисм бо ҳалли баробари суммаи Leetcode

arr = [0,2,1,-6,6,-7,9,1,2,0,1]
true

Шарҳ: Азбаски мо массивро ба се сегменти ҷамъи баробар тақсим карда метавонем. Ҳамин тариқ, мо гуфта метавонем, ки массивро ба се суммаи баробар тақсим кардан мумкин аст. Расман бештар, 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1.

arr = [0,2,1,-6,6,7,9,-1,2,0,1]
false

Шарҳ: Азбаски ҳеҷ гуна роҳи ба се қисмати алоҳида тақсим кардани массив вуҷуд надорад, ки ҷамъашон якхела бошад. Ҳамин тавр ҷавоб дурӯғ аст.

Усули массиви тақсимот ба се қисм бо ҳалли баробари суммаи Leetcode

Масъалаи тақсимоти тақсимот ба се қисм бо ҳалли баробари Leetcode Solution аз мо пурсид, ки оё мо массиви додашударо ба се зергурӯҳҳои ҷудошуда тақсим карда метавонем, ки ҷамъашон баробар бошанд. Пас, барои ҳалли масъала аввал мо бояд миқдори умумии массивро ёбем. Агар маблағи умумӣ ба 3 тақсим карда нашавад, пас ҷавоб дурӯғ аст. Зеро дар он сурат ҳеҷ гуна роҳи ба се зерқисми баробар тақсим кардани массив вуҷуд надорад. Аммо агар маблағ ба 3 тақсим карда шавад. Мо месанҷем, ки ба сум / 3 расида метавонем. Мо ин равандро бо нигоҳ доштани ҷамъи пайвастаи элементҳо, то он даме, ки ҷамъи онҳоро ба ҷамъи / 3 баробар кунем, тақлид мекунем. Агар мо ҷамъро то унсури ҷорӣ = sum / 3 гирем, тоталро ба 0 барқарор мекунем. Ва бори дигар ба ёфтани миқдори унсурҳо = sum / 3 оғоз кунед. Агар мо бо ин усул сум / 3 -ро 3 маротиба ба даст орем. Мо итминон дода метавонем, ки мо массивро ба 3 қисм тақсим мекунем, агар не.

рамз

Коди C ++ барои массиви тақсимот ба се қисм бо ҳалли баробари суммаи Leetcode

#include <bits/stdc++.h>
using namespace std;

bool canThreePartsEqualSum(vector<int>& arr) {
    int sum = 0;
    for(int i=0;i<arr.size();i++)
        sum += arr[i];
    if(sum % 3 != 0)
        return false;
    int sum3 = sum/3, partitions = 0;
    sum = 0;
    for(int i=0;i<arr.size();i++){
        sum += arr[i];
        if(sum == sum3){
            ++partitions;
            sum = 0;
        }
    }
    return partitions >= 3;
}

int main() {
  vector<int> arr({0,2,1,-6,6,-7,9,1,2,0,1}); 
  cout<<canThreePartsEqualSum(arr);
  return 0;
}
true

Рамзи Java барои массиви тақсимот ба се қисм бо ҳалли баробари суммаи Leetcode

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
  public static boolean canThreePartsEqualSum(int[] arr) {
        int sum = 0;
        for(int i=0;i<arr.length;i++)
            sum += arr[i];
        if(sum % 3 != 0)
            return false;
        int sum3 = sum/3, partitions = 0;
        sum = 0;
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
            if(sum == sum3){
                ++partitions;
                sum = 0;
            }
        }
        return partitions >= 3;
    }
 
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {0,2,1,-6,6,-7,9,1,2,0,1};
 
    System.out.print(canThreePartsEqualSum(arr));
  }
}
true

Таҳлили мураккабӣ

Мураккабии вақт

O (N), гарчанде ки мо массивро ду маротиба тай кардем. Аммо ин ҳамчун мураккабии вақти хаттӣ ҳисоб карда мешавад, зеро давраҳое, ки мо мегузарем, аз андозаи он вобаста нестанд.

Мураккабии фазо

О (1), зеро мо шумораи доимии унсурҳоро истифода мебурдем ва дар бораи ҳар як нишондиҳанда баъзе маълумоти мушаххасро нигоҳ намедоштем. Мураккабии фазо доимист.