新媒体网站建设费用详单,企业信息公开查询,做域名后就得做网站吗,网店代运营十大排名文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;暴力枚举方法二#xff1a;哈希表方法三#xff1a;二分法方法四#xff1a;双指针 知识回顾写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢… 文章目录 写在前面Tag题目来源题目解读解题思路方法一暴力枚举方法二哈希表方法三二分法方法四双指针 知识回顾写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【双指针】【二分法】【哈希表】【数组】 题目来源
面试经典150 | 167. 两数之和 II - 输入有序数组 题目解读
给定一个下标从 1 开始按照 非递减顺序排列 的整数数组 numbers找出两数之和等于 target 的两个数返回它们的下标其中每个整数只能使用一次题目保证只有唯一的答案。 解题思路
本题属于基础题与 1. 两数之和 解法基本一致。现在有三种解法如下。
方法一暴力枚举
一个比较容易想到的方法就是枚举所有可能的两数组合使用两层枚举第一层枚举第一个整数第二层枚举第二个整数。本题的数据量为 1 0 4 10^4 104两层枚举的时间复杂度为 1 0 8 10^8 108勉强可以通过。
具体地在枚举中判断两数之和是否等于 target如果相等直接返回对应的下标。
因为每个元素只可以使用一次并且两数先后出现的顺序没有要求因此 第二层枚举的整数可以从第一层枚举的整数的后一个位置开始。
实现代码
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int n numbers.size();for (int i 0; i n; i) {for (int j i1; j n; j) {if (numbers[i] numbers[j] target) {return {i 1, j 1};}}}return {-1, -1}; // 本题保证一定有解程序不会运行到此处}
};但是实测中最后几个测试用例超时了
复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。
空间复杂度 O ( 1 ) O(1) O(1)。
方法二哈希表
方法一中的时间复杂度可以优化到 O ( n l o g n ) O(nlogn) O(nlogn) 和 O ( n ) O(n) O(n)先来介绍时间复杂度为 O ( n ) O(n) O(n) 的方法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) 的方法将在方法三中介绍。
我们在枚举第二个整数的时候可以事先用一个哈希表来记录下所有整数以及位置这样枚举第二个整数的时间复杂度可以降为 O ( 1 ) O(1) O(1)但是需要一个额外的空间。
具体地可以先一次遍历 numbers记录每个整数以及下标记录完毕后枚举第一个加数在哈希表中查找第二个加数以上的过程可以用一个循环就可以解决枚举第一个加数之后先在哈希表中查询有么有合适的第二个加数然后再将当前的加数放入哈希表中这样可以省去一次 for 循环。
实现代码
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {unordered_mapint, int idx;for (int i 0; i numbers.size(); i) {if (idx.find(target - numbers[i]) ! idx.end()) {int idx1 min(i, idx[target - numbers[i]]);int idx2 max(i, idx[target - numbers[i]]);return {idx1 1, idx2 1};}idx[numbers[i]] i;}return {-1, -1};}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为数组 numbers 的长度只要一次循环就可以枚举两个加数。
空间复杂度 O ( n ) O(n) O(n)记录整数以及位置所用的空间。
方法三二分法
在方法二中我们是利用哈希表来降低枚举的线性时间的我们还可以使用二分方法来降低线性枚举的时间复杂度。
前面两种方法中都没有用到题目中 非递减顺序排列 这一条件我们可以利用这种有序性进行二分查找第二个加数。
具体地枚举第一个加数假设下标为 i接着要在 numbers[i1,...,n-1] 中使用二分法查找 target - numbers[i]如果查找到直接返回两个加数的对应下标否则继续枚举第一个数查找。
实现代码
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int n numbers.size();for (int i 0; i numbers.size(); i) {int num1 numbers[i];auto it find(numbers.begin() i 1, numbers.end(), target - num1);if (it ! numbers.end()) {int j it - numbers.begin();return {i 1, j 1};}}return {-1, -1};}
};复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)枚举第一个数的时间复杂度为 O ( n ) O(n) O(n)在每次枚举中最坏需要二分查找 O(logn) 次才能找到合适的第二个加数。
空间复杂度 O ( 1 ) O(1) O(1)。
方法四双指针
以上三种都不是最优的现在介绍时间复杂度和空间复杂度都是最优的方法——双指针。
初始左右两个指针 l e f t left left 和 r i g h t right right 分别指向 numbers 的第一个位置和最后一个位置。每次计算两个指针指向的整数之和与 target 进行比较
如果 numbers[left] numbers[right] target直接返回 {left 1, right 1}因为下标从 1 开始如果 numbers[left] numbers[right] target则将 right 指针左移一位如果 numbers[left] numbers[right] target则将 left 指针右移移位。
为什么两数之和小了右移 left 就可以了右移 right 不可以吗为什么两数之和大了左移 right 就可以了左移 left 不可以吗
假设 numbers[i] numbers[j] target 是唯一解其中 0 i j n-1。初始时 left 0、right n-1除非初始的时候左右两个指针已经位于 i、j 处否则一定是左指针先到达下标 i或者右指针先到达下标 j
左指针先到达下标 i 时右指针还在 j 的右侧此时 numbers[left] numbers[right] target于是需要将 right 指针左移一位这样才能缩小两数之和右指针先到达下标 j时左指针还在 i 的左侧此时 numbers[left] numbers[right] target于是需要将 left 指针右移一位这样才能增加两数之和。
于是就有了以上所示的双指针更新规则。
实现代码
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int n numbers.size();int l 0, r n - 1;while (l r) {int sum numbers[l] numbers[r];if (sum target) {--r;}else if (sum target) {l;}else {return {l1, r1};}}return {-1, -1};}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)双指针相向移动它们 一共最多走 n 次。
空间复杂度 O ( 1 ) O(1) O(1)使用的额外变量只有两个指针。 知识回顾
今天来看看 C \texttt{C} C 中二分查找的几个 API。
find() 使用二分法来查找数组中指定值的位置其返回的是迭代器
如果顺利查找到指定元素则返回该元素位置迭代器如果没有查找到指定元素则返回尾后迭代器
通过位置迭代器与首位置迭代器作差可以得到该元素在数组中的位置。
lower_bound() 和 upper_bound() 的含义与用法可以参考 【二分查找】几种基本题型你会了吗。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
