Java solution with list and map


  • 1

    This problem can be treated as a problem to find the number of paths to a destination island.

    • Each possible sum is one island
    • Our goal is to count the number of paths from island 0 to island S
    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
    
            int n = nums.length;
            if (n == 0) return 0;
    
            // Map<current sum, number of ways to current sum>
            List<Map<Integer, Integer>> dp = new ArrayList<>(n);
    
            dp.add(new HashMap<Integer, Integer>());
            if (nums[0] == 0) {
                // 0 is the corner case
                dp.get(0).put(nums[0], 2);
            } else {
                dp.get(0).put(-nums[0], 1);
                dp.get(0).put(nums[0], 1);
            }
    
            for (int i=1; i<n; ++i) {
                Map<Integer, Integer> curMap = new HashMap<>();
                Map<Integer, Integer> preMap = dp.get(i-1);
    
                for (Map.Entry<Integer, Integer> entry : preMap.entrySet()) {
                    int sumPlus = entry.getKey() + nums[i];
                    int curNum = curMap.containsKey(sumPlus) ? curMap.get(sumPlus) : 0;
                    curMap.put(sumPlus, entry.getValue() + curNum);
    
                    int sumMinus = entry.getKey() - nums[i];
                    curNum = curMap.containsKey(sumMinus) ? curMap.get(sumMinus) : 0;
                    curMap.put(sumMinus, entry.getValue() + curNum);
                }
    
                dp.add(curMap);
            }
    
            Integer result = dp.get(n-1).get(S);
            if (result == null) {
                result = 0;
            }
    
            return result;
        }
    }
    

Log in to reply
 

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