【Leetcode】 1013. 将数组分成和相等的三个部分

Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Example 1:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 
0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
1
2
3
4

Example 2:

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

Example 3:

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 
3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
1
2
3
4

---

Thought:

1. 首先计算整个数组的和 s，如果 s 不能被 3 整除，那么无法分成三个和相等的部分，直接返回 false。

2. 计算目标和 target，即每个部分的和。

3. 从数组的第一个元素开始遍历，累加元素的值，如果累加和等于 target，就说明找到了第一个部分的结束位置。

4. 从第一个部分的结束位置的下一个元素开始遍历，累加元素的值，如果累加和等于 target 的两倍，说明找到了第二个部分的结束位置。

5. 如果找到了第二个部分的结束位置，那么剩下的元素就是第三个部分，直接返回 true。

6. 如果遍历完整个数组都没有找到第二个部分的结束位置，那么无法分成三个和相等的部分，返回 false。

---

AC：

/*
 * @lc app=leetcode.cn id=1013 lang=cpp
 *
 * [1013] 将数组分成和相等的三个部分
 */

// @lc code=start
static const auto _ = []()
{
    ios::sync_with_stdio(false); // 关闭输入输出流同步，加速cin和cout的执行
    cin.tie(nullptr); // 解除cin与cout的绑定，加速cin的执行
    return nullptr;
}();

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int s = accumulate(arr.begin(), arr.end(), 0); 
        // 计算数组arr的总和
        if(s % 3 != 0) 
        // 如果总和不能被3整除，则无法将数组分成和相等的三个部分
        {
            return false;
        }
        int target = s / 3; 
        // 计算每个部分的目标和
        int n = arr.size(), i = 0, cur = 0;
        while(i < n) 
        // 找到第一个部分的结束位置
        {
            cur += arr[i];
            if(cur == target)
            {
                break;
            }
            i++;
        }
        if(cur != target) 
        // 如果第一个部分的和不等于目标和，则无法将数组分成和相等的三个部分
        {
            return false;
        }
        int j = i + 1;
        while(j + 1 < n) 
        // 找到第二个部分的结束位置
        {
            cur += arr[j];
            if(cur == target * 2)
            {
                return true;
            }
            j++;
        }
        return false; 
        // 如果无法找到第二个部分的结束位置，则无法将数组分成和相等的三个部分
    }
};
// @lc code=end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

Supplements:

static const auto _ = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
1
2
3
4
5
6

这段代码的主要作用是关闭输入输出流的同步，从而加速输入输出的速度。适合在进行大量输入输出操作时使用，例如需要读取多个数据的情况下。

在 C++ 中，输入输出流默认是同步的。这就意味着，每次进行输入输出操作时，都需要等待所有之前的输入输出操作完成后才能进行。

而使用上述代码可以关闭同步机制，从而提高输入输出速度。具体来说，这段代码的作用是：

1. 关闭输入输出流的同步；
2. 解除 cin 和 cout 之间的关联；
3. 返回空指针，使代码更加简洁和清晰。

需要注意的是，这段代码不是必需的，且在某些情况下可能导致程序出现问题。因此，在使用之前需要考虑清楚是否真正需要关闭同步机制。