算法题：求01字符串01个数相等的最长两区间

题目描述：给定一个01字符串S（字符串中只包含0、1两种字符），求两个区间s1、s2，要求这两个区间的0、1字符的个数相等，且区间最长，两区间可重叠但不重合。

例子：S=“11011”，s1=[0,3]，s2=[1,4]时，满足要求，且区间最长为4。

解法

namespace DataStructure {
    internal class Program {
        static void Main(string[] args) {
            // 输入数据
            string text = string.Empty;
            while (!IsZeroOneString(text))
                text = Console.ReadLine();
            Console.WriteLine(text + ":");
            Console.WriteLine(SolveProblem(text));
            Console.ReadKey();
        }

        static bool IsZeroOneString(string text) {
            return !string.IsNullOrWhiteSpace(text) &&
                   !text.Split('0', '1').Where(t => t != "").Any();
        }

        static (int, int, int, int) SolveProblem(string text) {
            int N = text.Length;
            int x1 = -1, y1 = -1, x2 = -1, y2 = -1;

            // 求前缀和
            var prefixSums = new int[N + 1];
            for (int i = 0; i < N; i++)
                prefixSums[i + 1] = prefixSums[i] + (text[i] == '1' ? 1 : 0);

            // 用字典记录数据<区间1数量,区间起点号>，遍历每种区间长度时先清空该字典
            var dict = new Dictionary<int, List<int>>();
            // l表示区间长度
            for (int l = N - 1; l > 0; l--) {
                dict.Clear();
                // i表示区间起点索引
                for (int start = 0; start < N - l + 1; start++) {
                    int end = N + start - 2;
                    int oneNum = prefixSums[end + 1] - prefixSums[start];
                    if (!dict.ContainsKey(oneNum)) {
                        dict[oneNum] = new List<int>();
                    }
                    dict[oneNum].Add(start);
                    if (dict[oneNum].Count == 2) {
                        x1 = dict[oneNum][0];
                        y1 = l + x1 - 1;
                        x2 = dict[oneNum][1];
                        y2 = l + x2 - 1;
                        return (x1, y1, x2, y2);
                    }
                }
            }
            return (x1, y1, x2, y2);
        }
    }
}

思路：

• 累积和数组prefixSums：时间复杂度是O(n)，有了这个数据后，可以在O(1)事件内求任一区间中0和1的个数，[x,y]区间1的个数是prefixSums[y+1]-prefixSums[x]。
• 从区间长度为n-1开始遍历，以(区间长度，区间中1个数)为key，将区间起点记录在字典dict中，字典值是一个数组，记录着相同区间长度、相同1个数的所有区间起点。由于只需要找到两个区间，当这个数组长度到2时，就已经找到了。
• 从区间长度为n-1开始遍历，找到即可终止算法，因为已经是尽可能长的区间了。
• 不用在字典中同时记录所以种类长度的区间信息，搜索每一种长度之前可清空字典。

总结

前缀和+字典，两者组合可以很好解决这类问题，注意朝这个方向思考。