用等和的Leetcode解決方案將陣列分為三部分


難度級別 容易獎學金
經常問 亞馬遜 Microsoft微軟
排列

問題分區 排列 用相等的總和分成三個部分Leetcode解決方案為我們提供了一個數組或向量,並詢問該序列是否存在三個分區。 在這裡,通過劃分,我們的意思是存在兩個索引i,j,以便從開始到第i個索引的元素之和等於從第i + 1到第j個索引的元素之和。 從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解決方案將數組分為三部分的問題問我們是否可以將給定的數組分為三個總和相等的不相交的子數組。 因此,首先要解決該問題,我們需要找到數組的總和。 如果總和不能被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(1), 因為我們使用了恆定數量的元素,並且沒有存儲有關每個索引的某些特定信息。 空間複雜度是恆定的。