Тэгш кодын шийдэл бүхий гурван хэсэгт хуваах массив


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Microsoft-
Array

Асуудал Array Leetcode Solution-тэй тэнцүү гурван хэсэгт бид массив эсвэл векторыг өгч, дарааллын гурван хуваалт байгаа эсэхийг асууна. Энд хуваалт гэж бид эхлэлээс ith индекс хүртэлх элементүүдийн нийлбэр нь i + 1-ээс jth индекс хүртэлх элементүүдийн нийлбэртэй тэнцүү байх i, j гэсэн хоёр индекс байна гэсэн үг юм. 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

Тайлбар: Массивыг ижил нийлбэртэй гурван тусдаа хэсэгт хуваах арга байхгүй тул. Тиймээс хариулт нь худлаа юм.

Leetcode-ийн ижил шийдэл бүхий гурван хэсэгт хуваах массивын хандлага

Leetcode Solution-тэй тэнцүү нийлбэр бүхий гурван хэсэгт хуваах массив нь өгөгдсөн массивыг тэнцүү нийлбэртэй гурван салангид дэд хуваарилалтад хувааж болох эсэхийг биднээс асуув. Тиймээс асуудлыг шийдэхийн тулд массивын нийт нийлбэрийг олох хэрэгтэй. Хэрэв нийт нийлбэр нь 3-т хуваагдахгүй бол хариулт нь худлаа болно. Учир нь массивыг гурван тэнцүү дэд хэсэгт хуваах арга байхгүй. Гэхдээ нийлбэр нь 3-т хуваагдах юм бол бид нийлбэр / 3-т хүрч чадах эсэхийг шалгана. Элементүүдийн тасралтгүй нийлбэрийг нийлбэр / 3-тэй тэнцүү байх хүртэл нь хадгалах замаар бид энэ процессыг дууриана. Хэрэв бид одоогийн элемент = sum / 3 болтол нийлбэрийг авбал нийлбэрийг 0 болгоно. Тэгээд дахин элементүүдийн нийлбэр = sum / 3-ийг олж эхэлнэ. Хэрэв бид энэ аргаар нийлбэр / 3-ийг 3 удаа авч чадвал. Бид массивыг 3 хэсэгт хувааж болно гэж өөрөөр хэлье.

код

Хэсэг массивыг гурван хэсэгт хувааж тэгшитгэлтэй Leetcode шийдэл бүхий C ++ код

#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

Хэсгийн массивыг гурван хэсэгт хувааж тэгшитгэлтэй Leetcode шийдэл бүхий Java код

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), Учир нь бид олон тооны элемент ашигладаг байсан бөгөөд индекс тус бүрийн талаархи тодорхой мэдээллийг хадгалаагүй болно. Сансрын нарийн төвөгтэй байдал нь тогтмол байдаг.