share my map-based DP solution (Java)

  • 0

    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) {
                return 0;
            Map<Integer, Integer>[] buffer = new Map[nums.length];
            buffer[0] = new HashMap<Integer, Integer>();
                buffer[0].put(0, 2);  //<--!!! Tricky
                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())
                    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.