Բաժանման զանգվածը երեք մասի հավասար գումարի Leetcode լուծմամբ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Microsoft
Դասավորություն

Խնդիրը Բաժանում Դասավորություն Հավասար գումարով երեք մասի մեջ Leetcode Solution- ը մեզ տալիս է զանգված կամ վեկտոր և հարցնում, թե արդյոք հաջորդականության հնարավոր է երեք բաժին: Այստեղ, բաժանում ասելով, մենք նկատի ունենք, որ կա երկու ցուցանիշ, j այնպես, որ տարրերի հանրագումարը սկզբից մինչև ինդեքս հավասար է տարրերի հանրագումարին `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 ++ կոդ ՝ Partition Array- ի երեք մասերի հավասար գումարի 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 կոդ ՝ Partition Array- ի մեջ երեք մասի հավասար գումարի 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), չնայած մենք երկու անգամ թերթել ենք զանգվածը: Բայց դա կհամարվի որպես գծային ժամանակի բարդություն, քանի որ այն զանգվածը, որը մենք անցնում ենք, կախված չէ դրա չափից:

Տիեզերական բարդություն

O (1), քանի որ մենք օգտագործել ենք հաստատուն թվով տարրեր և չենք պահպանել որոշակի ինդեքսներ յուրաքանչյուր ցուցանիշի վերաբերյալ: Տիեզերական բարդությունը կայուն է: