【口试】leetcode一题多解之towSum

开发者 · 2024-9-27 10:39:03

这是leetcode口试刷题一题多解系列的第一篇，跟各人聊下我写这个系列的初衷，作为前端开辟要不要学习大概口试算法这个话题争论已久，各有说辞，在这我不做评判，只从我个人前端从业履历出发，谈谈我对算法学习的一点见解：
* 初入前端的开辟者可能会和算法比力远，重点在页面的开辟和后端的交互上，但是算法还是可以资助你更好的构造数据结构，提高代码的服从终极提拔页面的相应速率。
* 有肯定履历的前端开辟，可能会资助团队的小搭档办理一些疑难标题，而很多标题都必要你对框架和库有较深入的明白，可能会涉及到一些算法干系的知识。
* 如果对某一些前端细分范畴感兴趣的同砚好比图形处置处罚、动画效果等，算法可能会在一些复杂标题的处置处罚上提供很大的资助。
末了在这越来越卷的形势下，前端口试对于算法的要求也越来越多，以是前端对于算法的学习上，不管是为了更有效的办理标题还是去做底层的框架库，亦大概就是为了口试高薪，都越来越有须要学习了。
这个系列是一题多解系列，每一道题我都会给出两种或两种以上的方法去办理，目标不但仅是为了优化，
更是为了拓展头脑，给各人提供各种差别办理标题的思绪，可能资助会更大些。
标题

本日跟各人一起看一道经典的 leetcode 算法题，两数之和。

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按恣意次序返复兴案。

题解1---暴力遍历

这是最简单也是最直接的一种思绪，就是两层循环遍历求和，如果便是 target，则返回效果，时间复杂度是 O(n^2),空间复杂度 O(1)。
题解2---哈希缓存

从题解可以看到第一层遍历我们实在无法制止，而第二层的遍历目标是找到 target - x, 如果我们把全部遍历过的数据存储在哈希表里，当我们必要去查找的时间，直接去取就行了，如许就从 O(N) 的复杂度减到了 O(1)。

这是一个经典的以空间换时间的头脑，使用哈希表举行缓存，从而减少遍历的查询次数，这个思绪非经常见,如果背面我们遇到遍历的时间，可以想一想能不能在遍历的过程当中，存储一些信息，而这些信息会在后续的利用过程中有效，那么通常是可以或许低沉时间复杂度的，但是由于增长的hash的存储，以是通常空间复杂度会提拔。
题解3---双指针法

有些情况下数据是有某种特点的，我们可以使用这个特点举行算法的编写，会有效很多，固然这个例子数据自身没有特点，但是我们可以先举行排序，创造一个特殊的序列，在一个有序的数组中就可以用双指针法举行查找。
上面代码先举行排序，然后就可以在有序的数组上使用双指针对序罗列行查找，使用数据自身特点举行算法的编写在后续的算法系列中经常会遇见。时间复杂度为 O(NlogN),空间复杂度为 O(1)。
本日用了三种方法对 twoSum 举行了求解，除了暴力解法，重要是举行数据缓存，用空间换时间的头脑，尚有就是使用数据自身特点举行算法筹划，很多情况，数组有序了，对其举行的查找复杂度都比力低。

【口试】leetcode一题多解之towSum

所属分类: 问答交流

新帖推荐: 30日

推荐作品