Direct Map Solution, Don't need sum.


  • 0
    G
    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            Map<Integer, Integer>[] map = new HashMap[nums.length+1];
            map[0] = new HashMap<Integer,Integer>();
            map[0].put(0,1);
            for(int i = 0; i< nums.length; i++){
                map[i+1] = new HashMap<Integer, Integer>();
                for(Map.Entry<Integer,Integer> entry: map[i].entrySet()){
                    int nkey = entry.getKey()+nums[i];
                    map[i+1].put(nkey, map[i+1].getOrDefault(nkey,0) + entry.getValue());
                    nkey = nkey-2*nums[i];
                    map[i+1].put(nkey, map[i+1].getOrDefault(nkey,0) + entry.getValue());
                }
            }
            return map[nums.length].getOrDefault(S,0);
        }
    }
    

Log in to reply
 

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