Share my DP&Map solution, one pass


  • 10
    S
    public int findMaxLength(int[] nums) {
    	int n = nums.length, res = 0;
    	Map<Integer, Integer> map = new HashMap<>();
    	int[][] dp = new int[n+1][2];
    	for (int i = 1; i < dp.length; i++) {
    		if (nums[i-1] == 0) {
    			dp[i][0] = dp[i-1][0]+1;
    			dp[i][1] = dp[i-1][1];
    		}else {
    			dp[i][0] = dp[i-1][0];
    			dp[i][1] = dp[i-1][1]+1;
    		}
    		if (dp[i][0] == dp[i][1]) res = Math.max(res, dp[i][0]*2);
    		else {
    			int dif = dp[i][1]-dp[i][0];
    			if (map.containsKey(dif)) res = Math.max(res, 2*(dp[i][0]-dp[map.get(dif)][0]));
    			else map.put(dif, i);
    		}
    	}
    	return res;
    }
    

  • 0
    J

    @shawloatrchen Can you explain your logic? Thanks!


  • 1

    If you want to do it in one pass, it can be done in a much simpler way:

        public int findMaxLength(int[] nums) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>() {{put(0,0);}};
            int maxLength = 0, runningSum = 0;
            for (int i=0;i<nums.length;i++) {
                runningSum += nums[i];
                Integer prev = map.get(2*runningSum-i-1);
                if (prev != null) maxLength = Math.max(maxLength, i+1-prev);
                else map.put(2*runningSum-i-1, i+1);
            }
            return maxLength;
        }
    
    

  • 0
    S

    @jamescsi
    Use dp[][] to store the zeros and ones from start to current position
    and use map to store the difference of ones and zeros with index;
    if current position ones-zeros = 2, we check map if there is other position ones-zeros=2
    if we find, the 2*(current index - that index) is candidate
    the max candidate is the answer


  • 0
    J

    @shawloatrchen thanks a lot


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.