[Swift]LeetCode525. 连续数组 | Contiguous Array_app

概述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: 2Explanation: [0, 1] is the longest contiguous subarray with equ

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: 2Explanation: [0,1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

input: [0,1,0]Output: 2Explanation: [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 的最长连续子数组（的长度）。

示例 1:

输入: [0,1]输出: 2说明: [0,1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: [0,0]输出: 2说明: [0,1] (或 [1,0]) 是具有相同数量0和1的最长连续子数组。

注意: 给定的二进制数组的长度不会超过50000。

760ms

 1 class Solution { 2     func findMaxLength(_ nums: [Int]) -> Int { 3         var map = [Int: Int]() 4         map[0] = -1 5          6         var maxLength = 0 7         var count = 0 8         for i in 0..<nums.count { 9             count += nums[i] == 1 ? 1 : -110             if let v = map[count] {11                 maxLength = max(maxLength,i - v)12             } else {13                 map[count] = i14             }15         }16         17         return maxLength18     }19 }

804ms

 1 class Solution { 2     func findMaxLength(_ nums: [Int]) -> Int { 3         let nums = nums.map { (n: Int) -> Int in 4             if n == 0 {  5                 return -1  6             } else {  7                 return 1  8             } 9         }10         var preSum: [Int: Int] = [:] // sum - index11         preSum[0] = -112         var sum = 013         var res = 014         for i in 0 ..< nums.count {15             sum += nums[i]16             if preSum[sum] != nil {17                 res = max(res,i - preSum[sum]!)  18             } else {19                 preSum[sum] = i20             }21         }22         return res23     }24 }

Runtime: 812 ms Memory Usage: 19.7 MB

 1 class Solution { 2     func findMaxLength(_ nums: [Int]) -> Int { 3         var res:Int = 0 4         var n:Int = nums.count 5         var sum:Int = 0 6         var m:[Int:Int] = [0:-1] 7         for i in 0..<n 8         { 9             let num:Int = (nums[i] << 1) - 110             sum += num11             if m[sum] != nil12             {13                 res = max(res,i - m[sum]!)14             }15             else16             {17                 m[sum] = i18             }19         }20         return res21     }22 }

904ms

 1 class Solution { 2     func findMaxLength(_ nums: [Int]) -> Int { 3         if nums.isEmpty { return 0 } 4          5         var sums = [Int: (Int?,Int?)]() 6         sums[0] = (-1,nil) 7  8         var sum = 0 9         for i in 0..<nums.count {10             sum += (nums[i] == 1) ? 1 : -111             if sums[sum] == nil {12                 sums[sum] = (i,nil)13             } else {14                 sums[sum]!.1 = i15             }16         }17         18         var ret = 019         for (sum,pair) in sums {20             if pair.1 != nil {21                 ret = max(ret,pair.1! - pair.0!)22             }23         }24         return ret25     }26 }

976ms

 1 class Solution { 2     func findMaxLength(_ nums: [Int]) -> Int { 3         let n = nums.count 4         if n == 0 { return 0 } 5         var max = [Int](repeating: 0,count: n) 6         var count_ones = [Int](repeating: 0,count: n) 7         for i in 0..<n { 8             if i == 0 { count_ones[i] = nums[0] } 9             else { count_ones[i] = count_ones[i-1] + nums[i] }10         }11         12         max[n-1] = 013         var i = n-214         var res = 015         while i >= 0 {16             var diff = (nums[i] == 1 ? 1 : -1)17             var j = i18             while diff != 0 && j < n {19                 let next_j = j + abs(diff)20                 if next_j >= n { break }21                 let ones = (count_ones[next_j] - count_ones[j])22                 let zeros = (next_j - j) - ones23                 diff = diff + ones - zeros24                 j = next_j25             }26             27             if diff == 0 {28                 max[i] = (j-i+1) + (j < n-1 ? max[j+1] : 0)29             }30             31             if res < max[i] { res = max[i] }32             33             i -= 134         }35         36         return res37     }38 }

1160ms

 1 class Solution { 2     func findMaxLength(_ nums: [Int]) -> Int { 3         var map: [Int: [Int]] = [:] 4         var curr = 0 5         map[0] = [0] 6          7         for i in 0..<nums.count { 8             var bin = nums[i] 9             10             if (bin == 1) {11                 curr += 112             }13             else {14                 curr -= 115             }16                 17             if let _ = map[curr] {18                 map[curr]!.append(i+1)19             }20             else {21                 map[curr] = [i+1]22             }23         }24         25         return getMaxLengthFromMap(map)26     }27     28     func getMaxLengthFromMap(_ map: [Int: [Int]]) -> Int {29         var maxL = 030         31         for key in map.keys {32             let indexes = map[key]!33             if indexes.count > 1 {34                 var tempMax = indexes[indexes.count-1] - indexes[0]35                 36                 maxL = max(maxL,tempMax)37             }38         }39         40         return maxL41     }42 }