1013. Partition Array Into Three Parts With Equal Sum

LeetCode easy оригинал: C# #array #bit-manipulation #csharp #easy #leetcode #search

LeetCode Static

Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Пример:

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

Output: true

C# решение

сопоставлено/оригинал

public class Solution {
    public bool CanThreePartsEqualSum(int[] arr) {
        int totalSum = arr.Sum();
        if (totalSum % 3 != 0) {
            return false;
        }
        
        int target = totalSum / 3, partSum = 0, count = 0, n = arr.Length;
        
        for (int i = 0; i < n; i++) {
            partSum += arr[i];
            if (partSum == target) {
                count++;
                partSum = 0;
                if (count == 2 && i < n - 1) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CanThreePartsEqualSum(vector<int>& arr) {
        int totalSum = arr.Sum();
        if (totalSum % 3 != 0) {
            return false;
        }
        
        int target = totalSum / 3, partSum = 0, count = 0, n = arr.size();
        
        for (int i = 0; i < n; i++) {
            partSum += arr[i];
            if (partSum == target) {
                count++;
                partSum = 0;
                if (count == 2 && i < n - 1) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public boolean CanThreePartsEqualSum(int[] arr) {
        int totalSum = arr.Sum();
        if (totalSum % 3 != 0) {
            return false;
        }
        
        int target = totalSum / 3, partSum = 0, count = 0, n = arr.length;
        
        for (int i = 0; i < n; i++) {
            partSum += arr[i];
            if (partSum == target) {
                count++;
                partSum = 0;
                if (count == 2 && i < n - 1) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

JavaScript решение

сопоставлено/оригинал

class Solution {
    canThreePartsEqualSum(arr) {
        const totalSum = arr.reduce((sum, num) => sum + num, 0);
        if (totalSum % 3 !== 0) {
            return false;
        }
        
        const target = totalSum / 3;
        let partSum = 0, count = 0;
        
        for (let i = 0; i < arr.length; i++) {
            partSum += arr[i];
            if (partSum === target) {
                count++;
                partSum = 0;
                if (count === 2 && i < arr.length - 1) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total_sum = sum(arr)
        if total_sum % 3 != 0:
            return False
        
        target = total_sum // 3
        part_sum, count, n = 0, 0, len(arr)
        
        for i in range(n):
            part_sum += arr[i]
            if part_sum == target:
                count += 1
                part_sum = 0
                if count == 2 and i < n - 1:
                    return True
        
        return False

Go решение

сопоставлено/оригинал

func canThreePartsEqualSum(arr []int) bool {
    totalSum := 0
    for _, num := range arr {
        totalSum += num
    }
    if totalSum % 3 != 0 {
        return false
    }
    
    target := totalSum / 3
    partSum, count, n := 0, 0, len(arr)
    
    for i := 0; i < n; i++ {
        partSum += arr[i]
        if partSum == target {
            count++
            partSum = 0
            if count == 2 && i < n - 1 {
                return true
            }
        }
    }
    
    return false
}

Algorithm

Вычисление общей суммы:

Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой.

Поиск первой и второй части:

Итерируйте по массиву и ищите первую часть с суммой, равной одной трети от общей суммы. Продолжайте итерацию для поиска второй части с такой же суммой.

Убедитесь, что между первой и второй частью есть хотя бы один элемент.

Проверка третьей части:

Убедитесь, что оставшаяся часть массива также имеет ту же сумму, что и две найденные части. Если да, вернуть true, иначе false.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.