Leetcode 525. Contiguous Array

[Woodyiiiiiii]

这道题问题是如何在O(n)时间复杂度内完成所有subArray的遍历。(O(nlgn)不太可能)

考虑如何最大利用化题目条件。即，如何利用binary array条件和1和0数目相等条件呢？

既然只能遍历一遍，只能用累加和preSum来记录数据，那如何遍历subArray呢？用HashMap存储之前的累加和信息，要满足题意，1和0的数目相等的subArray，可以先将0变成-1，这样如何1和-1数目相等，那就和之前的存储的map值相等，从而定位subArray的范围了。

class Solution {
    public int findMaxLength(int[] nums) {
        
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        
        // convert all 0 to -1
        for (int i = 0; i < nums.length; ++i) {
            nums[i] = nums[i] == 0 ? -1 : nums[i];
        }
        
        // preSum
        int sum = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                int last = map.get(sum);
                res = Math.max(res, i - last);
            } else {
                map.put(sum, i);
            }
        }
        
        return res;
        
    }
}v

---

参考资料：

• https://leetcode.com/problems/contiguous-array/
• 类似题目523. Continuous Subarray Sum