Simple JA DP solution using map - 190 ms


  • 0
    S
        public int findTargetSumWays(int[] nums, int S) {
            int n = nums.length;
            if(n==1) return Math.abs(nums[0])==Math.abs(S)?1:0;
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            map.put(0,1);
            for(int i=0;i<n;i++){
                Map<Integer,Integer> newmap = new HashMap<Integer,Integer>();
                for(Integer sum:map.keySet()){
                    int cnt = map.get(sum);
                    int addsum= sum+nums[i];
                    int addcnt = newmap.getOrDefault(addsum, 0);
                    newmap.put(addsum,addcnt+cnt);
                    int minorsum= sum-nums[i];
                    int minorcnt = newmap.getOrDefault(minorsum, 0);
                    newmap.put(minorsum,minorcnt+cnt);
                }
                map=newmap;
            }
            return map.get(S)==null?0:map.get(S);
        }

Log in to reply
 

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