د برابر سم لیټکوډ حل سره دریو برخو ته د تقسیم لړۍ


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د Microsoft
پیشه

ستونزه برخه پیشه د مساوي Sum لیټکوډ حل سره دریو برخو ته موږ ته د صف یا ویکتور چمتو کوي او پوښتنه کوي چې ایا د ترتیب درې برخې شتون لري. دلته ، د تقسیم په واسطه زموږ مطلب دا دی چې دلته دوه شاخصونه دي i ، j داسې چې د پیل څخه تر بیټ انډیکس پورې د عناصرو مجموعه له i + 1 څخه تر jth انڈیکس پورې د عناصرو مجموعې سره مساوي ده. او وروستي عنصر ته د j + 1 شاخص څخه د عناصرو مجموعه د صفونو لومړي دوه برخو سره هم مساوي ده. که چیرې داسې دوه شاخصونه شتون ولري ، موږ وایو چې سرنی په مساوي مقدار سره په دریو برخو ویشل کیدی شي ، نه. مخکې لدې چې حل ته حرکت وکړئ راځئ چې یو څو مثالونه وګورو.

د برابر سم لیټکوډ حل سره دریو برخو ته د تقسیم لړۍ

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

توضیحات: له دې امله چې دلته په دریو جلا برخو ویشلو کې کومه لاره شتون نلري چې ورته پیسې لري. پدې توګه ځواب غلط دی.

د برابر برخه لیټکوډ حل سره دریو برخو ته د برخې اراضي لپاره لاره

د مساوي Sum لیټکوډ حل سره درې برخو کې د برخې تقسیم سیرم موږ څخه وپوښتل چې ایا موږ وکولی شو ورکړل شوی صف په دریو ګډوډو فرعي برخو ویشو چې مساوي پیسې لري. نو ، د ستونزې حل کولو لپاره لومړی موږ اړتیا لرو د صفونو مجموعه ومومئ. که ټوله برخه د 3 لخوا تقسیم نه شي ، نو ځواب غلط دی. ځکه چې بیا هیڅ لاره شتون نلري چې صف په دریو مساوي فرعي برخو وویشي. مګر که دا رقم په 3 سره ویشل کیدی شي موږ به وګورو چې ایا موږ رقم / 3 لاسته راوړو. موږ د عناصرو دوامداره مجموعې ذخیره کولو سره دا پروسه تقلید کوو تر هغه چې موږ د دوی مجموعې / 3 سره مساوي ومومو. که چیرې موږ تر اوسني عنصر = مجموع / 3 پورې مجموعه ترلاسه کړو ، نو موږ 0 ته بیا راګرځول. او یوځل بیا ، د عناصرو مجموعه = موندنه پیل کړئ = لنډ / 3. که موږ د دې میتود په واسطه پیسې / 3 3 ځله ترلاسه کړو. موږ ډاډ ترلاسه کولی شو چې موږ کولی شو صف په 3 برخو ویشلو نور نه.

کوډ

C ++ کوډ د مساوي Sum 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

د مساوي Sum لیټکوډ حل سره درې برخو کې د برخې اره کې د برخې لپاره جاوا کوډ

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) ، که څه هم موږ دوه ځله صفونه تیر کړي. مګر دا به د خطي وخت پیچلتیا په توګه حساب شي ځکه چې هغه وختونه چې موږ د صف څخه تیر شو هغه د هغې په اندازې پورې اړه نلري.

د ځای پیچلتیا

O (1) ، ځکه چې موږ د عنصرونو دوامداره شمیره کارولې او د هرې شاخص په اړه ځینې ځانګړي معلومات ندي ذخیره کړي. د ځای پیچلتیا مستقل ده.