题目描述

对称子字符串

Description
Given a string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits.

Input
输入第一行是测试用例的个数，后面每一行表示一个数字组成的字符串，例如：”123123”

Output
输出找到的满足要求的最长子串的长度。例如，给定的例子长度应该是 6。每行对应一个用例的结果。

Sample Input 1
1
1538023

Sample Output 1
4

分析

题目中有几个关键信息，就是子字符串长度为偶数，且子字符串左侧之和与右侧之和相同。
在判断奇偶时可以使用位运算，即与1做与运算，即：

1
2
3
4
5
6
if ( n & 1 == 1) {
	// n为奇数
}
else { 
    // n为偶数
}

题解

首先是通用的获取输入的方法

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args)
{
    Scanner scanner = new Scanner(System.in);
    int numOfTestCases = Integer.parseInt(scanner.nextLine());
    while (numOfTestCases-- > 0)
    {
        String input = scanner.nextLine();
        System.out.println(calLongestLength(input.toCharArray()));
    }
}

解法一：暴力法

遍历所有长度为偶数的子字符串，判断这些字符串的左半部分和右半部分的和是否相同。
以下是暴力法的题解，i表示从字符串第一个字符处开始遍历，第二个for循环中j从i的下一个字符处开始遍历，索引值每次加2，因为题目要求子字符串长度必须为偶数，此时j-i+1就是子字符串的长度了。然后再进行第三层循环，计算子字符串的左半部分的和以及右半部分的和，然后判断左半部分的和与右半部分的和是否相同，最后更新最大的字符串长度值。
这里要注意的是，子字符串左半部分和右半部分索引的取值。举例来说：
原字符串： 1 2 3 4 4 3 2 1
此时假设i=0，j=3，则字符串长度为4，左半部分是1 2，索引为0、1，右半部分是3 4，索引为2 、3，k从0开始遍历到2（k最多取1），
则inputArray[i+k]刚好是inputArray[0]、inputArray[1]，即取到1和2，右侧inputArray[i+k+lengthOfCurSubString/2]刚好取到inputArray[2]、inputArray[3]。
当原字符串是奇数也是同理。

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
private static int calLongestLength(char[] inputArray)
{
    if (inputArray == null || inputArray.length == 0)
    {
        return 0;
    }
    int lengthOfInput = inputArray.length;
    int maxLen = 0;
    for (int i = 0; i < lengthOfInput; i++)
    {
        for (int j = i + 1; j < lengthOfInput; j += 2)
        {
            int lengthOfCurSubString = j - i + 1;

            int leftSum = 0;
            int rightSum = 0;
            for (int k = 0; k < lengthOfCurSubString / 2; k++)
            {
                leftSum += (inputArray[i + k] - '0');
                rightSum += (inputArray[i + k + lengthOfCurSubString / 2] - '0');
            }
            if (leftSum == rightSum && maxLen < lengthOfCurSubString)
            {
                maxLen = lengthOfCurSubString;
            }
        }
    }
    return maxLen;
}

时间复杂度：O(n3)

解法二 截取法

在解法一种，我们遇到了计算连续的子数组和的问题，因此自然会想到使用截取法来优化计算
代码如下所示。
注意，这里的关键点是索引的选取。sumSoFarArray数组用于记录到目前为止数组的和，sumSoFarArray[0] = 0，因此sumSoFarArray[i]表示inputArray[0]+inputArray[1]+…+inputArray[i-1]+inputArray[i]，即inputArray中第i个元素之前的和（包括这第i个元素，此处i从1开始取），实际上是等于sumSoFarArray[i]，因此当for循环时，索引i是从0开始取的，对应以下代码中，j表示子数组的右侧最后一个元素的位置，那么从第一个元素到j这个元素的和，应该是sumSoFarArray[j+1]。
此外，还有middleIndex，这个表示的是子数组的中间元素的位置，可以发现，它实际上表示的是右半部分的第一个元素
举例来说，还是以上面原数组是1 2 3 4 5 6 7 8 为例，此时i=1，j=4，子数组是2 3 4 5，middleIndex = 3，表示的是4这个元素，是右半部分的第一个元素。而sumSoFarArray[3]表示前三个元素的和，因此右半部分的和为sumSoFarArray[j + 1] - sumSoFarArray[middleIndex]，左侧同理。

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
private static int calLongestLengthByIntercept(char[] inputArray)
{
    if (inputArray == null || inputArray.length == 0)
    {
        return 0;
    }
    int lengthOfInput = inputArray.length;
    int maxLen = 0;
    // 该数组表示到目前为止的和
    int[] sumSoFarArray = new int[lengthOfInput + 1];
    sumSoFarArray[0] = 0;
    for (int i = 1; i < lengthOfInput + 1; i++)
    {
        sumSoFarArray[i] = sumSoFarArray[i - 1] + (inputArray[i - 1] - '0');
    }

    for (int i = 0; i < lengthOfInput; i++)
    {
        for (int j = i + 1; j < lengthOfInput; j++) // 这里也可以写成j = j + 2，则下面不用判断curSubArrayLength的奇偶性了
        {
            int curSubArrayLength = j - i + 1;
            if ((curSubArrayLength & 1) == 1)
            {
                continue;
            }
            int middleIndex = i + curSubArrayLength / 2;
            if (sumSoFarArray[j + 1] - sumSoFarArray[middleIndex] == sumSoFarArray[middleIndex] - sumSoFarArray[i])
            {
                maxLen = Math.max(curSubArrayLength, maxLen);
            }
        }
    }
    return maxLen;
}

解法二的时间复杂度是O(N2)，用到了额外的O(N)的空间

解法三 中心扩散法

这个解法的意思是，从字符串的中点出发，同时往左右两侧扩展，计算左右两侧的和，如果相同则更新子字符串的最大值。
代码如下：

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
private static int calLongestLengthByExpandMid(char[] inputArray)
{
    if (inputArray == null || inputArray.length == 0)
    {
        return 0;
    }
    int lengthOfInput = inputArray.length;
    int maxLen = 0;
    for (int i = 0; i < lengthOfInput - 1; i++)
    {
        int leftIndex = i;
        int rightIndex = i + 1;
        int leftSum = 0;
        int rightSum = 0;
        while (rightIndex < lengthOfInput && leftIndex >= 0)
        {
            leftSum += inputArray[leftIndex] - '0';
            rightSum += inputArray[rightIndex] - '0';
            if (leftSum == rightSum)
            {
                maxLen = Math.max(maxLen, rightIndex - leftIndex + 1);
            }
            leftIndex--;
            rightIndex++;
        }
    }
    return maxLen;
}

解法三的时间复杂度是O(N2)，空间复杂度为O(1)

相关题目

[1]最长回文子串
[2]字符串回文相关题目