share my map-based DP solution (Java)


  • 0
    M

    The following is my HashMap-based solution.
    I try to cache the count of each intermediate values, and current result is based on the previous ones.
    Any idea to improve efficiency? Thanks

    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            if(nums.length==0)
                return 0;
            
            Map<Integer, Integer>[] buffer = new Map[nums.length];
            buffer[0] = new HashMap<Integer, Integer>();
            if(nums[0]==0)
                buffer[0].put(0, 2);  //<--!!! Tricky
            else{
                buffer[0].put(nums[0], 1); 
                buffer[0].put(-nums[0], 1); 
            }
            
            for(int i=1; i<nums.length; i++){
                buffer[i] = new HashMap<Integer, Integer>(); 
                Map<Integer, Integer> pre = buffer[i-1];
                
                for( int val : pre.keySet() ){
                    int t = val+nums[i];
                    buffer[i].put( t, buffer[i].getOrDefault(t, 0) + pre.get(val) ); 
                    
                    t = val-nums[i];
                    buffer[i].put( t, buffer[i].getOrDefault(t, 0) + pre.get(val) ); 
                }
            }
            
            int result=0;
            for(int val : buffer[buffer.length-1].keySet())
                if(val==S)
                    result += buffer[buffer.length-1].get(val);
            
            return result; 
        }
    }
    

Log in to reply
 

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