昨天做了到利用HashMap的Sum类型题,感觉其思路挺有意思的,联想到LeetCode第一题Two Sum的高效解法也是用的HashMap,所以在此归纳总结下这类题目的深层次理解。

Two sum(1)——(无序数组)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] index = new int[]{0, 1};
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (hm.containsKey(target - nums[i])) {
                index[1] = i;
                index[0] = hm.get(target - nums[i]);
            } else {
                hm.put(nums[i], i);
            }
        }
        return index; 
    }
}

一开始我的想法是很粗暴的,就是想每两个值加起来和target比较一下,但是实际上这效率太低,实际使用可以在之后的数数组中找是否有target-i的数,没有的话用一个map记录每个值和其序号,便于后面的寻找。

Two Sum II(167)——(排序数组)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
   public int[] twoSum(int[] numbers, int target) {
        int l = 0;
        int r = numbers.length - 1;
        while (numbers[l] + numbers[r] != target) {
            if (numbers[l] + numbers[r] > target) {
                r--;
            } else {
                l++;
            }
        }
        return new int[]{l + 1, r + 1};
    }
}

利用其有序性,设立两个标志从左右加,将其和与target比较即可。

Two Sum IV(653)——(TODO)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int l = 0;
        int r = list.size() - 1;
        while (l < r) {
            int sum = list.get(l) + list.get(r);
            if (sum == k) {
                return true;
            } else if (sum > k) {
                r--;
            } else {
                l++;
            }
        }
        return false;
    }

    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

BST的中序遍历是有序的,问题就简化为上一小题了,但是这种方法并不高效,之后可以改进。

Subarray Sum Equals K(560)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
   public int subarraySum(int[] nums, int k) {
       int count = 0;
        int sum = 0;
        Map<Integer,Integer> hashmap = new HashMap<>();
        hashmap.put(0,1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (hashmap.containsKey(sum-k)){
                count+= hashmap.get(sum-k);
            }
            hashmap.put(sum, hashmap.getOrDefault(sum,0)+1);
        }
        return count;
   }
}

这道题提供了一个新思路,如果我想遍历长度的5的各种可能性,我改怎么办?比如我想试试1,2,3,4,5;{1,2}{2,3}{3,4}等等直到{1,2,3,4,5};这道题的告诉我们可以用sum[j]-sum[i]的方式,并将其值存在map里面,map的存的是sum[i]即按序累加的值,当sum[j]-sum[i]的时候,就可以出现各种子情况了。

Combination Sum(39)——(DEBUG)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<List<Integer>>();
        helper(new ArrayList<Integer>(),candidates,0,target);//new出来的不要具体说明的嘛?
        return res;
    }
    private void helper(List<Integer> list, int[] candidates, int start, int remain){
        if (remain == 0){
            res.add(new ArrayList<>(list));//为什么不直接add list呢?
            return;
        }
        else{
            for (int i = start; i < candidates.length; i++) {
                if (remain<candidates[i]){
                    continue;
                }
                list.add(candidates[i]);
                helper(list,candidates,i,remain-candidates[i]);
                list.remove(list.size()-1);
            }
        }
    }
}

这道题利用了dfs的思路,而且同样使用了sum题基本思路,把本来加起来的sum变成remain(target-nums[i]),这样在不断的dfs的时候,remain的值不断变化。这道题还要注意到的是数据可以重复利用,所以其start的值不需要每层加1;最后要注意的是dfs到底部发现不满足的话要把最靠近底部的值给弹出去;add(list)的时候要用new出来的,负责list的内容会是最终状态,这个之后debug再理解。

Path Sum(112)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        return helper(root, sum, 0);
    }

    private boolean helper(TreeNode root, int sum, int temp) {
        if (root == null) {
            return false;
        }
        temp += root.val;
        if (root.left == null && root.right == null && temp == sum) {
            return true;
        }
        return helper(root.left, sum, temp) || helper(root.right, sum, temp);
    }
}

PathSum的第一题简单,都是老套路,dfs的时候把remain或者sum值放在函数里面传递。

Path Sum II(113)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
   List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<Integer> temp = new ArrayList<>();
        helper(root, sum, 0, temp);
        return res;
    }

    private void helper(TreeNode root, int sum, int num, List<Integer> temp) {
        if (root == null) {
                return;
            }
            temp.add(root.val);
            num += root.val;
            if (root.left == null && root.right == null && num == sum) {
                res.add(new ArrayList<Integer>(temp));
                temp.remove(temp.size()-1);
                return;
            }else{
                helper(root.left, sum, num, temp);
                helper(root.right, sum, num, temp);
            }
            temp.remove(temp.size()-1);
    }
}

这道题融合了PathSum的性质和CombinationSum的要求,就是把数组找出来,这样我们需要在dfs函数上加一个temp的list来记录当前遍历的数组内容,再设一个全局list变量来作为return的ans,其他思路照旧。

Path Sum III(437)——(DEBUG)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int res = 0;
    Map<Integer, Integer> map;

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        map = new HashMap<>();
        map.put(0, 1);
        helper(root, sum, 0);
        return res;
    }

    private void helper(TreeNode root, int sum, int tempSum) {
        if (root == null) {
            return;
        }
        tempSum += root.val;
        res += map.getOrDefault(tempSum - sum, 0);//??????
        map.put(tempSum, map.getOrDefault(tempSum, 0) + 1);
        helper(root.left, sum, tempSum);
        helper(root.right, sum, tempSum);
        map.put(tempSum, map.get(tempSum) - 1);//?????????

    }
}

之前两道pathsum都是说好从根节点到子节点的,这到题就没说了,这样按照之前的思路,我们需要一个map来记录;最后照旧,需要在dfs后把尾部弹出,不过这里还不是很理解,要再看看。

Target Sum(494)——(TODO)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        helper(nums, 1, S - nums[0]);
        helper(nums, 1, S + nums[0]);
        return count;
    }

    private void helper(int[] nums, int index, int target) {
        if (index == nums.length) {
            if (target == 0) {
                count++;
            }
            return;
        }
        helper(nums, index + 1, target - nums[index]);
        helper(nums, index + 1, target + nums[index]);
    }
}

两种dfs中的方式,一种是存sum的累加值,一种是放taregt-nums[i]的值,两种方式的详细区别之后在看看。明天改成sum的形式。