【Leetcode】2422. Merge Operations to Turn Array Into a Palindrome

题目地址：

https://leetcode.com/problems/merge-operations-to-turn-array-into-a-palindrome/description/

给定一个长$n$数组$A$，每一步允许将某一段整个替换为这一段的和。问要将$A$变为回文至少需要多少步。题目保证$A_i>0$。

只考虑$n>1$，如果$A[0]=A[n-1]$，那么最优方案一定不会去合并头尾两个数（如果合并，则两端都要参与合并，和都不参与合并是等价的，也可以得最优解）。如果$A[0]\ne A[n-1]$，那么我们必须先在两端凑出相等的和，否则无法回文。而凑出相等的和，可以用双指针来做。凑出相等的和之后，问题就转为了规模更小的问题了，从而得以解决。代码如下：

class Solution {
 public:
  int minimumOperations(vector<int>& a) {
    int n = a.size(), res = 0;
    long lsum = a[0], rsum = a.back();
    for (int i = 0, j = n - 1; i < j;)
      if (lsum < rsum) {
        i++;
        lsum += a[i];
        res++;
      } else if (lsum > rsum) {
        j--;
        rsum += a[j];
        res++;
      } else {
        i++, j--;
        lsum = a[i], rsum = a[j];
      }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度$O(n)$，空间$O(1)$。