समान Sum Leetcode समाधानको साथ तीन भागहरूमा विभाजन एर्रे


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन माइक्रोसफ्ट
एरे

समस्या विभाजन एरे तीन भागमा बराबर Sum Leetcode समाधानले हामीलाई एर्रे वा भेक्टर प्रदान गर्दछ र अनुक्रमको तीन विभाजनहरू छन् कि भनेर सोध्छ। यहाँ विभाजन द्वारा हाम्रो मतलब त्यहाँ दुई सूचकांकहरू i, j जस्तै कि सुरुबाट ith सूचकांकमा तत्त्वहरूको योग i + १ बाट jth अनुक्रमणिकाको योगफल बराबर हुन्छ। र अन्तिम तत्वमा j + १ अनुक्रमणिकाबाट तत्त्वहरूको योग पनि एर्रेको पहिलो दुई खण्डहरू बराबर छ। यदि त्यहाँ त्यस्ता दुई सूचकहरू छन् भने हामी भन्छन एरे बराबर रकमको साथ तीन भागमा विभाजन गर्न सकिन्छ, अन्यथा। समाधानमा जानु अघि हामी केही उदाहरणहरू हेरौं।

समान Sum Leetcode समाधानको साथ तीन भागहरूमा विभाजन एर्रे

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

स्पष्टीकरण: किनकि हामी एरे लाई बराबर योगको तीन खण्डमा विभाजन गर्न सक्छौं। त्यसैले हामी भन्न सक्दछौं कि एरे तीन बराबर योगफलमा विभाजन गर्न सकिन्छ। अधिक औपचारिक रूपमा, ० + २ + १ = -0 + - - + + + + १ = २ + ० + १।

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

स्पष्टीकरण: किनकि एरेलाई तीन छुट्टै सेक्सनमा विभाजित गर्ने कुनै तरिका छैन जुन समान योगफलहरू छन्। यसैले उत्तर गलत छ।

बराबर योग लेटकोड समाधानको साथ तीन भागहरूमा विभाजन एर्रेको लागि दृष्टिकोण

समान विभाजन लेटकोड समाधानको साथ तीन भागमा समस्या विभाजन एर्रेले हामीलाई सोध्यो यदि हामी दिइएको एर्रेलाई तीन बेग्लाबेगारी सबारीमा विभाजित गर्न सक्छौं कि बराबर योगफलहरू छन्। त्यसो भए पहिले समस्या समाधान गर्न हामीले एरेको कुल योग फेला पार्नु पर्छ। यदि कुल योग by ले भाग गर्न मिल्दैन, भने उत्तर गलत छ। किनभने त्यसो भए एरेलाई तीन बराबर उप-भागहरूमा विभाजन गर्न कुनै तरिका छैन। तर यदि योग 3. ले भाग गर्न मिल्छ भने हामी जोड / 3 प्राप्त गर्न सक्दछौं कि भनेर जाँच गर्नेछौं। हामी यस प्रक्रियाहरूको नक्कल गर्दछौं तत्वहरूको अविरल योग भण्डार गरेर जब सम्म हामीले उनीहरूको कुल योगफल / to सँग मिल्दैन। यदि हामीले हालको एलिमेन्ट = योग / until सम्म कुल प्राप्त गर्छौं भने हामी कुल ० लाई रिसेट गर्छौं। र फेरि फेरी, तत्वहरूको योग = योग / finding देख्न सुरु गर्दछ। यदि हामी यस विधिबाट योग / 3 पटक प्राप्त गर्न सक्छौं। हामी आश्वासन दिन सक्छौं कि हामी एर्रेलाई parts भागहरु मा विभाजन गर्न सक्दछौं अन्य छैन।

कोड

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 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), यद्यपि हामीले दुई पटक एर्रे ट्र्याभर्स गरेका छौं। तर यो लाईख समय जटिलताको रूपमा गणना हुनेछ किनकि समयहरू हामी एर्रे पार गर्दछौं यसको साइजमा निर्भर हुँदैन।

ठाउँ जटिलता

O (१), किनकि हामीले तत्वहरूको स्थिर संख्या प्रयोग गर्‍यौं र प्रत्येक अनुक्रमणिकाको सम्बन्धमा केही खास जानकारी भण्डार गर्दैनौं। ठाउँ जटिलता स्थिर छ।