【LeetCode】525. Contiguous Array 解题报告（Python & C++）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]

Output: 2

Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]

Output: 2

Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

题目大意

找到一个数组中的一个连续数组，使得这个连续数组中0和1的数字一样多。

解题方法

累积和

使用的方法是求和+hashmap的方法，首先从头开始遍历，如果当前值是0就sum-1，否则就sum+1.这样如果得到了一个sum就知道在此之前出现了1的个数和0的个数的差值。因此，当后面该sum再次出现的时候，我们就知道了这个差值再次出现，也就是说，从第一次这个差值出现和第二次这个差值出现之间0和1的个数是一样多的。

因此我们需要一个map来保存0和1的差值。如果这个差值没出现过就给它赋值为它出现的索引。我们要求的就是当同样的差值出现的时候，两者之间的最大值。另外注意，当这个差值再次出现的时候不要更新map。即我们的策略是只保存这个差值出现的第一个位置，只有这样我们才知道最长的连续子数组是多少。

这个题的官方解答里面给出了详细的每一步的变化过程，推荐一看。

也可以在刚开始的时候就把nums中的0替换成-1，这样就可以直接使用total_sum加上当地前数值即可。

需要注意的是字典应该有个初始化值，代表在刚开始的时候没有任何元素的位置是-1，否则后面出现0的时不能和最开始的位置求位置差。

python代码如下：

class Solution:

    def findMaxLength(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        print(nums)

        total_sum = 0

        index_map = dict()

        index_map[0] = -1

        res = 0

        for i, num in enumerate(nums):

            if num == 0:

                total_sum -= 1

            else:

                total_sum += 1

            if total_sum in index_map:

                res = max(res, i - index_map[total_sum])

            else:

                index_map[total_sum] = i

        return res

C++代码如下：

class Solution {

public:

    int findMaxLength(vector<int>& nums) {

        const int N = nums.size();

        unordered_map<int, int> m_;

        for (int& num : nums) {

            if (num == 0) {

                num = -1;

            }

        }

        m_.insert({0, -1});

        int sums = 0;

        int res = 0;

        for (int i = 0; i < N; ++i) {

            sums += nums[i];

            if (m_.count(sums)) {

                res = max(res, i - m_[sums]);

            }

                m_.insert({sums, i});

            }

        }

        return res;

    }

};

参考资料：

https://leetcode.com/problems/contiguous-array/discuss/99646/Easy-Java-O(n)-Solution-PreSum-+-HashMap
https://leetcode.com/articles/contiguous-array/

日期

2018 年 9 月 12 日 ———— 做题还是要有耐心

巴特西

【LeetCode】525. Contiguous Array 解题报告（Python & C++）

目录

题目描述

题目大意

解题方法

累积和

日期

最新文章

热门文章