题目名称

第39题：组合总和(中等)

第41题：缺失的第一个正数(困难)

第42题：接雨水(困难)

补充：个人项的题解，没有图解，没有视频。

第39题：组合总和

题目描述

给定一个无重复元素的数组candidates 和一个目标数target ，找出candidates 中所有可以使数字和为target的组合。candidates 中的数字可以无限制重复被选取。数组中所有元素都是正数，解集不能重复。

说明

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

解题思路

这种题型，只有回溯这一种解法，涉及到回溯，所谓回溯，就是稍微有一点技巧的穷举法，穷举法一般意味着高空间利用率和时间利用率，因此只要涉及到回溯，就要考虑剪枝。其次，遇到无序数组，如果题目没有要求时间复杂度必须在O(n)，一般情况下都可以去排序，而本题在排序后可以达到剪枝的效果。

完整代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        dfs(candidates, target, ans, new ArrayDeque<Integer>(), 0);
        return ans;
    }

    public void dfs(int[] candidates, 
                    int target, 
                    List<List<Integer>> ans, 
                    Deque<Integer> path,
                    int begin){
        if(target == 0){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i = begin; i < candidates.length; i++){
          // 这一步是剪枝操作，很好理解
            if(candidates[i] > target) return;
            path.addLast(candidates[i]);
            dfs(candidates, target - candidates[i], ans, path, i);
            path.removeLast();
        }
    }

第41题：缺失的第一个正数

问题描述

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

时间复杂度: $O(n)$

空间复杂度: $O(1)$

说明

1 2	输入: [1,2,0] 输出: 3

解题思路

时间复杂度O(n)：只能进行遍历的操作
空间复杂度O(1)：所有操作必须是原地的

这两点带来的局限性，导致了本题必须要抓住一个关键点：一个长度为n的数组nums，其序列中如果没有缺失的正数，则$nums[i] == i$，也就是说，如果在这个数组的idx位置其值不是idx+1，则这个位置的数就是缺失的。因此，这道题的解题思路就确定了：使数组idx位置的值可判断，不一定非要$nums[idx] == idx + 1$，也可以使idx位置的值为负(题解) 。本题将$nums[idx] == idx +１$。

完整代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums.length == 0) return 1;
        for(int i = 0; i < nums.length; i++){
            exchange(nums, nums[i]);
        }
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i+1) return i+1;
        }
        return nums[nums.length - 1] + 1;
    }

    public void exchange(int[] nums, int num){
      // 递归出口：位置上的值是正确的值，或者超出了范围
        if(num <= 0 || num > nums.length || nums[num - 1] == num) return;
        else{
            int temp = nums[num - 1];
            nums[num - 1] = num;
            exchange(nums, temp);
        }
    }

第42题：接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解题思路

这题比较难，我的第一反应特别蠢：从底向上一层层遍历，看每一层最多能接收多少雨水。这样的时间复杂度是$O(MN)$，LC直接通过不了。实际上这道题是有好的思路的，核心想法就是：确定每个idx位置上能装多少雨水。而每个idx上装雨水的量，取决于在这个位置左右两端最高的那堵墙，因此如果我们知道每个位置上左右两端的最高位置，则可以完成计算：$res = Math.min(leftMax[idx], rightMax[idx]) - height[idx]$

完整代码

class Solution {
    public int trap(int[] height) {
        int len = height.length, ans = 0;
        if(len == 0 || len == 1) return 0;
        int[] leftMax = new int[len];
        leftMax[0] = height[0];
        int[] rightMax = new int[len];
        rightMax[len - 1] = height[len - 1];
        for(int i = 1; i < len; i++){
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
      // 这一步有点技巧，确定右边最大的值需要从右到左遍历
        for(int i = len - 2; i >= 0; i--){
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        for(int i = 0; i < len; i++){
            ans += Math.min(leftMax[i], rightMax[i]) - height[i]; 
        }
        return ans;
    }

复杂度

时间复杂度：$O(n)$，只进行了遍历操作
空间复杂度：$O(n)$，保存了每个idx位置左右两端的最大值

补充

这道题其实还有更好的解法：双指针法，空间复杂度降到了$O(1)$，这种方法特别巧妙，利用了从左到右和从右到左两种不同的状态来计算在idx位置上可以存的雨水。但是这种方法在面试时是很难想出来的，因此这里就不赘述了。