【LeetCode】HOT 100（6）

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

目录

题单介绍：

题目：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：39. 组合总和 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

---

题目：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

    }
};

解题思路：

这道题看一眼题目，然后看到时间复杂度的要求，

马上就能知道，暴力过不了，必须要二分，

总体思路就是用二分查找左右边界即可，

具体思路如下：

通过二分查找出题目要求的target所在的位置（nums[mid] == target）

然后分两种情况，

如果是查找左边界，就一直更新右边界靠过去

如果是查找右边界，就一直更新左边界靠过去

代码如下：

代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return {search_range(nums, target, "left"), search_range(nums, target, "right")};
    }
private:
    int search_range(const vector<int>& nums, int target, const string& side) {
        int left = 0, right = nums.size() - 1;
        int res = -1;
        while(left <= right) {
            int mid = (left + right) >> 1;
            if(nums[mid] < target) { //经典二分
                left = mid + 1;
            }
            else if(nums[mid] > target) {
                right = mid - 1;
            }
            else { //nums[mid] == target
                res = mid;
                if(side == "left") { //更新右边界靠过去
                    right = mid - 1;
                }
                if(side == "right") { //更新左边界靠过去
                    left = mid + 1;
                }
            }
        }
        return res;
    }
};

过过过过啦！！！！

题目：39. 组合总和 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

    }
};

解题思路：

这道题他说的组合数不超过150个，马上就想到，这不得暴力拿下，

直接暴力的话好像有一些问题，同一个数可以多次选取，用循环不好实现，

那这个时候我就想到搜索了，dfs拿下这道题问题不大，

代码如下：

代码：

class Solution {
public:
    vector<int> v; //每个合格的数组（sum == target）
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res; //存返回的数组
        dfs(candidates, res, target, 0, 0); //搜索
        return res;
    }
private:
    void dfs(const vector<int>& candidates, vector<vector<int>>& res,
            int target, int sum, int begin) {
        if(sum == target) { //符合条件
            res.push_back(v);
            return;
        }
        if(sum > target) return; //剪枝
        for(int i = begin; i < candidates.size(); i++) { //搜索
            v.push_back(candidates[i]);
            dfs(candidates, res, target, sum + candidates[i], i);
            v.pop_back(); //回溯
        }
    }
};

过过过过啦！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~