从向量末端获取距离与仅仅计数背后的直觉

Question

我正在尝试解决一个 GeeksForGeeks question 如下：

数一数将一个数组分成总和相等的三个连续部分的方法的数量：给定一个 n 个数字的数组，找到个个索引对 i 和 j 使得 0 到 i-1 的元素之和等于 i 到 j 的元素之和等于从 j+1 到 n-1 的元素总和。对于输入 {1, 2, 3, 0, 3}，输出是 2（我们有索引：(0, 1), (2, 2) and (3, 4) and (0, 1), (2, 3 ) 和 (4, 4))

代码如下：

// C++ program to count number of ways we can 
// partition an array in three parts with equal 
// sum. 
#include<bits/stdc++.h> 
using namespace std; 

// binary search to find the number of required 
// indices in suffix array. Returns index of 
// first element which is greater than x. 
int binarysearch(vector <int> &v, int x) 
{ 
    int low = 0, high = v.size()-1; 
    while (low <= high) 
    { 
        int mid = (low + high)/2; 
        if (v[mid] <= x) 
            low = mid + 1; 
        else if (v[mid] > x && v[mid-1] <= x) 
            return mid; 
        else if (v[mid] > x && mid == 0) 
            return mid; 
        else
            high = mid-1; 
    } 
    return -1; 
} 

// function to calculate the number of ways to 
// divide the array into three contiguous parts 
int CountContiguousParts(int arr[] ,int n) 
{ 
    int count = 0; // initializing answer 

    // Creating and filling prefix array 
    int prefix[n]; 
    prefix[0] = arr[0]; 
    for (int i=1; i<n; i++) 
        prefix[i] = prefix[i-1] + arr[i]; 

    // Total sum of elements is equal to last 
    // value in prefix array. 
    int total_sum = prefix[n-1]; 

    // If sum of all the elements is not divisible 
    // by 3, we can't divide array in 3 parts of 
    // same sum. 
    if (total_sum%3 != 0) 
        return 0; 

    // Creating and filling suffix array 
    int suffix[n]; 
    suffix[n-1] = arr[n-1]; 
    for (int i=n-2; i>=0; i--) 
        suffix[i] = suffix[i+1] + arr[i]; 

    //<------Don't understand why we are doing things below------------->
    // Storing all indexes with suffix 
    // sum equal to total sum by 3. 
    vector <int> v; 
    for (int i=0; i<n; i++) 
        if (suffix[i] == total_sum/3) 
            v.push_back(i); 

    // Traversing the prefix array and 
    // doing binary search in above vector 
    for (int i=0; i<n; i++) 
    { 
        // We found a prefix with total_sum/3 
        if (prefix[i] == total_sum/3) 
        { 
            // Find first index in v[] which 
            // is greater than i+1. 
            int res = binarysearch(v, i+1); 

            if (res != -1) 
                count += v.size() - res; 
        } 
    } 

    return count; 
} 

// driver function 
int main() 
{ 
    int arr[] = {1 , 2 , 3 , 0 , 3}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << CountContiguousParts(arr, n); 
    return 0; 
}

我不遵循创建向量 v 存储后缀总和等于 (total sum/3) 的所有索引然后进行二进制搜索 return 的索引的逻辑第一个大于 i+1.

的元素

对于给定的示例 {1, 2, 3, 0, 3}，前缀数组为 {1, 3, 6, 6, 9}，而后缀数组为 {9, 8, 6, 3, 3}。因此，按照上述逻辑，对于前缀数组中索引 i=1 处的 3，我们在后缀数组中索引 i=3 处找到 3 并将 v.size() - res 添加到 count，这是我们在这里的答案 2。 但是，我不明白它的作用以及它如何给我们答案。

我想的是前缀数组中索引i=1处的3，我们应该计算[=28的出现次数=] 在后缀数组中开始 i+1 并且 return 计数。

有人可以详细说明上面的代码是 tryna 做什么吗？

Answer 1

您想将一个数组分成三部分，使每个部分的总和与其他部分的总和相等。假设我们的分区是 P1、P2、P3。我们想要这样的关系： P1=P2=P3=x

我们还有P1 + P2 + P3 = 3x = total sum of array

所以很明显，我们的数组之和必须是 3 的倍数，否则不可能将我们的数组划分为满足我们的要求。

 vector <int> v; 
for (int i=0; i<n; i++) 
    if (suffix[i] == total_sum/3) 
        v.push_back(i);

你同意 P3 应该包含数组总和的三分之一吗？使用上面的代码，我们只存储候选索引。

  for (int i=0; i<n; i++) 
    { 
        // We found a prefix with total_sum/3 
        if (prefix[i] == total_sum/3) 
        { 
            // Find first index in v[] which 
            // is greater than i+1. 
            int res = binarysearch(v, i+1); 

            if (res != -1) 
                count += v.size() - res; 
        } 
    }

然后用上面的代码我们也应用相同的逻辑首先我们计算前缀包括数组总和的三分之一让我们称之为 i 然后在 v （看第一个代码片段它包含的内容）我们搜索一个索引，其中它的值大于 i + 1 如果我们能找到这样的索引那么 P2 也可以创建让我们称之为 j(它是第一个大于 i + 1) 的索引）现在我们的分区看起来像这样：

[0 ..... i][i+1 ....j-1][j .... n]

现在下面的代码做的是：

    if (res != -1) 
        count += v.size() - res;

您是否同意 j 和 j 之后的所有索引，即 j+1, j+2, j+3, ... , v.size()-1 它们也满足我们的要求？即

[0 ..... i] [i+1 ....v[j-1]] [v[j] .... n]

[0 ..... i] [i+1 ....v[j]]   [v[j+1] .... n]

[0 ..... i] [i+1 ....v[j + 1]] [v[j+2] .... n]
...
[0 ..... i] [i+1 ....v[v.size()-2]] [v[v.size()-1] .... n]

它们都是相等的分区（v 包含原始数组的索引，因此如果我们选择值并转到原始数组并从那里求和到最后它的总和的三分之一原始数组）。此代码仅计算所有有效状态。并且算法继续，直到找到所有状态。

从向量末端获取距离与仅仅计数背后的直觉

Intuition behind getting distance from the end of vector versus just counting

c++

algorithm

logic