Contiguous Array
给一个0,1数组, 返回最长的0和1相等的子数组. 这个直接count也能做, 但是我看讨论中有一个解法更巧妙. 先把0变成-1, 以为n个0和1个0想加是没有区别的, 所以变成-1就可以知道有几个-1了, 然后只需要找相同的sum就可以找到-1和1的相同的位置, 只需要记录最多的个数就可以.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Solution { public int findMaxLength(int[] nums) { for(int i = 0 ; i < nums.length; i++){ if(nums[i] == 0) nums[i] = -1; } Map<Integer, Integer> map = new HashMap<>(); map.put(0,-1); int sum = 0; int max = 0; for(int i = 0 ; i < nums.length; i++){ sum += nums[i]; if(map.containsKey(sum)) max = Math.max(max, i - map.get(sum)); else map.put(sum,i); } return max; } } |