FilesExpand file tree

 master

/

ContiguousArray525.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

76 lines (70 loc) · 2.1 KB

 master

/

ContiguousArray525.java

Copy path

Top

File metadata and controls

• Code
• Blame

76 lines (70 loc) · 2.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

/**

* 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.

*

*/

public class ContiguousArray525 {

/**

* https://leetcode.com/problems/contiguous-array/solution/

*/

public int findMaxLength(int[] nums) {

int maxlen = 0;

for (int start = 0; start < nums.length; start++) {

int zeroes = 0, ones = 0;

for (int end = start; end < nums.length; end++) {

if (nums[end] == 0) {

zeroes++;

} else {

ones++;

}

if (zeroes == ones) {

maxlen = Math.max(maxlen, end - start + 1);

}

}

}

return maxlen;

}

public int findMaxLength2(int[] nums) {

int[] arr = new int[2 * nums.length + 1];

Arrays.fill(arr, -2);

arr[nums.length] = -1;

int maxlen = 0, count = 0;

for (int i = 0; i < nums.length; i++) {

count = count + (nums[i] == 0 ? -1 : 1);

if (arr[count + nums.length] >= -1) {

maxlen = Math.max(maxlen, i - arr[count + nums.length]);

} else {

arr[count + nums.length] = i;

}

}

return maxlen;

}

public int findMaxLength3(int[] nums) {

Map<Integer, Integer> map = new HashMap<>();

map.put(0, -1);

int maxlen = 0, count = 0;

for (int i = 0; i < nums.length; i++) {

count = count + (nums[i] == 1 ? 1 : -1);

if (map.containsKey(count)) {

maxlen = Math.max(maxlen, i - map.get(count));

} else {

map.put(count, i);

}

}

return maxlen;

}

}