参考

算法性能分析

时间复杂度

  • 时间复杂度
    算法的执行效率,算法的执行时间与算法的输入值之间的关系
  • 以下例子,设语句执行时间为a,b,c,假设循环10次,则此代码的执行时间为a+10b+c,通常省略成10b,为nb,b为系数可以省略不计,所以时间复杂度为O(n)
1
2
3
4
5
6
7
funtion ON(num){
var total = 0; //a
fot(var i=0;i<num;i++){
total += i; //b
}
return total; //c
}
  • 以下代码,a+b都是常数,与输入num无关,所以时间复杂度为O(1)
1
2
3
4
5
function O1(num){
var i=num; //a
var j=num*2; //b
return i+j;
}
  • 以下代码,while循环logN次,时间复杂度为O(logN)
1
2
3
4
5
6
7
function OlogN(num){
var i=1;
while(i<num){ //num=N
i = i*2; // N*a
}
return i;
}
  • 以下代码,外层循环m次,内层循环了alogN次,去掉常数系数,则时间复杂度为O(MlogN)
1
2
3
4
5
6
7
8
9
10
11
12
function ONLogN(num1,num2){
var total = 0;
var j = 0;
for(var i=0;i<num1;i++){ //num1=m
while(j < num2){ //num2=n
//以下两个语言时间为a
total += i + j;
j = j*2;
}
}
return total;
}
  • 下列代码,并列两个循环,执行时间Mb+Nc,去掉固定常数,则时间复杂度为O(M+N)
1
2
3
4
5
6
7
8
9
function OMN(num1,num2){
var total = 0;
for(var i=0;i<num1;i++){ //num1=M
total += i; //b -> M*b
}
for(var j=0;j<num2;j++){ //num2=N
total += j; //c -> N*c
}
}
  • 以下代码,外层执行N次,内存执行aN次,去掉常数系数,则时间复杂度O(N2)
1
2
3
4
5
6
7
8
9
function ON2(num){
var total = 0;
for(var i=0;i<num;i++){ //num=N
for(var j=0;j<num;j++){
total += i + j; //a
}
}
return total;
}
  • 对比

O(1)<O(logN)<O(N)<O(MlogN)<O(n2)<O(2n)<O(n!)

空间复杂度

  • 空间复杂度
    算法的存储空间输入值之间的关系

  • 以下代码,定义一个整型变量为4个字节,是不变的,空间复杂度为O(1)

1
2
3
4
5
6
7
funtion test(num){
var total = 0;
fot(var i=0;i<num;i++){
total += i;
}
return total;
}
  • 以下代码,定义一个整型数组,每一个元素所占4个字节,数组大小随参数nums变化,则所占空间为nums*4,则空间复杂度为O(n)
1
2
3
4
5
6
7
function test(nums){
var array[];
for(var i=0;i<nums;i++){
array.append(i);
}
return array;
}

两数之和

  • 题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标
  • 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍
  • 你可以按任意顺序返回答案
  • 官方解题答案:https://leetcode-cn.com/articles/two-sum/
1
2
3
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]

暴力法

  • 两个两个一组,双层循环遍历所有可能,判断之和是否相等,即可找出答案,比如找到数组第一个数和后面所有的数两两相加判断是否等于目标值;
  • 执行用68ms,内存消耗38.3MB
1
2
3
4
5
6
7
8
9
var twoSum = function(nums, target) {
for(var i=0;i<nums.length;i++){
for(var j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
return [i,j];
}
}
}
};

哈希表法

  • 首先构造哈希表map,哈希表是一种key:value的数据结构,用来存放数组的值和索引
  • 遍历数组 nums,i 为当前下标,每个值都判断map中是否存在 target-nums[i] 的 key 值,也就是给定值的另一半数字,比如9-2=7,查看map.key是否存在数字7
  • 如果存在则找到了两个值并判断索引不相等,如果不存在则将当前的 (nums[i],i) 存入 map 中,继续遍历直到找到为止
1
2
3
4
5
6
7
8
9
var twoSum = function(nums, target) {
var map=new Map(); //构造哈希表
for(var i = 0; i< nums.length; i++) { //遍历
if(map.has(target - nums[i])) { //查看是否存在目标值的另一个数字
return [map.get(target-nums[i]),i]; //返回下标
}
map.set(nums[i], i); //不存在就放入哈希表
}
}

两数相加

  • 给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位 数字,如果为两位数,取个位数并向后一位数进一
  • 请你将两个数相加,并以相同形式返回一个表示和的链表
  • 你可以假设除了数字 0 之外,这两个数都不会以 0 开头
  • 例如6+4=10,取个位数0并进一,4+3=7加上进的一位为7+1=8
  • 官方解题答案:https://leetcode-cn.com/articles/add-two-numbers/
1
2
3
4
5
6
7
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
//极端进位清空
输入:l1 = [9,9,9], l2 = [9,9]
输出:[8,9,0,1]
解释:999+99=1098

解题思路

  • 除法运算除10可以得到十位上的数(12/10=1),对10取余运算可以得到个位数(12%10=2)
  • 使用变量carry标记下一个数进位多少,并从包含最低有效位的表头开始模拟逐位相加的过程
  • 例如,5 + 7 = 12在这种情况下,我们会将当前位的数值设置为 2,并将进位 carry = 1带入下一次迭代。进位 carry必定是 0 或 1,这是因为两个数字相加(考虑到进位)可能出现的最大和为 9 + 9 + 1 = 19
  • 算法思路如下
    1. 创建一个dummy头结点,然后相加的结果依次添加串起来
    2. curr指针指向头结点,用于往后遍历,并将指向的当前结点初始化为返回链表的哑结点
    3. 将进位carry初始为0
    4. 遍历链表L1和L2直至到达它们的尾端
      • 设定sum=l1.val+l2.val+carry
      • 更新进位的值,carry=sum/10
      • 创建一个数值为(sum%10) 的新结点,并将其设置为当前结点的下一个结点,然后将当前结点前进到下一个结点
      • 同时,将l1和l2前进到下一个结点
    5. 检查最后 carry=1 是否成立,如果成立,则向返回列表追加一个含有数字 1 的新结点
    6. 返回哑结点的下一个结点
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
29
30
31
32
33
34
35
36
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode doummy = new ListNode(0); //初始一个返回链表的头结点
ListNode curr = doummy; //curr指针用来遍历链表
int carry=0; //定义进位变量,无进位为0,有进位为1
while( l1 != null || l2 != null){ //两个链表都不为空
int sum=0;
if( l1 != null){
sum += l1.val; //求和
l1 = l1.next; //移到下一位
}
if( l2 != null){
sum += l2.val; //求和
l2 = l2.next; //移到下一位
}
sum += carry; //再加上carry进位的值
curr.next=new ListNode(sum%10); //取个位上的数作为新结点加到当前指向的结点后面
carry = sum/10; //计算是否进位
curr = curr.next; //遍历指针移动到下一位
}
if(carry>0){ //判断最后carry进位是否为1
curr.next = new ListNode(carry); //如果为1,就作为结点加到后面
}
return doummy.next; //返回结果链表
}
}

无重复字符的最长子串

1
2
3
4
5
6
7
8
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",因为往后会遇到a,a会重复,所以其长度为 3。
-----
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
 请注意,你的答案必须是子串的长度,"pwke" 是一个子序列,不是子串。"pw"也不是,因为不是最长

滑动窗口

  • 滑动窗口sliding window
    其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!
  • 如何移动?
    我们只要把队列的左边的元素移出就行了,直到满足题目要求!一直维持这样的队列,找出队列出现最长的长度时候,求出解!
  • 算法思路
    1. 创建一个set
    2. 两个指针,第一个指向字符串的开头j,第二个随着for循环遍历字符串i
    3. 如果set里没有s[i], 说明目前为止还没有重复的字符,把s[i]添加到set里,然后更新最大不重复字符的数量,用maxLength变量存储,如果maxLength<set.size就更新,否则不更新
    4. 如果set里有s[i],则从set里开始删除s[j],并且递增,再检查set里是否有s[i],如此反复直到set里没有s[i]为止
    5. 重复步骤3和4,直到遍历完整个字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const set = new Set(); //创建一个set集合
let i = 0,j = 0,maxLength = 0; //创建两个指针和记录最大不重复字符数量的变量
if(s.length === 0){ //字符串为空
return 0;
}
for(i;i<s.length;i++){ //遍历字符串
if( ! set.has(s[i])){ //不重复情况,即set里没有s[i],则添加到set里
set.add(s[i]);
maxLength = Math.max(maxLength,set.size); //更新maxLength的值,保证为最大值
}else{ //出现重复情况
while(set.has(s[i])){ //如果set里有s[i],则从set里开始删除s[j]
set.delete(s[j]);
j++; //j后移一位
}
set.add(s[i]);
}
}
return maxLength;
};

最长回文子串

  • 给你一个字符串 s,找到 s 中最长的回文子串,即一个字符串正序和逆序都是一样的
1
2
3
4
5
6
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案
---
输入:s = "ac"
输出:"a"
  • 采用从中心向两边扩散的方法,例如babad,但不是每个字符串都有中心点,例如cabbad
  • 算法思路
    1. 如果字符串长度小于2,直接返回原字符串
    2. 定义两个变量,一个start存储当前找到的最大回文字符串的起始位置,另一个maxLength记录字符串的长度(终止位置就是start+ maxLength)
    3. 创建一个helper function,判断左边和右边是否越界,同时最左边的字符是否等于最右边的字符。如果以上三个条件都满足,则判断是否需要更新回文字符串最大长度及最大字符串的起始位置。然后将left--right++向两边扩散,继续判断,直到不满足三个条件之一。
    4. 遍历字符串,每个位置调用helper function两遍,第一遍检查i-1,i+1, 第二遍检查i;i+1,第一遍查询处理存在中心的情况(babad),第二遍查询处理不存在中心的情况(cabbad)
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
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if(s.length < 2){
return s;
}
let start = 0; //存储当前找到的最大回文字符串的起始位置
let maxLength = 1; //记录字符串的长度
function expandAroundCenter(left,right){ //helper function函数
while(left >= 0 && right <= s.length-1 && s[left] === s[right]){
if(right - left + 1 > maxLength){ //找到更大的回文字符串
maxLength = right - left +1;
start = left;
}
//向两边扩散
left --;
right ++;
}
}
for(let i = 0;i < s.length; i ++ ){ //每个元素都当作中心调用函数
expandAroundCenter(i-1,i+1);
expandAroundCenter(i,i+1);
}
return s.substring(start,start+maxLength); //截取字符串
};

三数之和

  • 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组
  • 注意:答案中不可以包含重复的三元组
1
2
3
4
5
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
---
输入:nums = [0]
输出:[]
  • 算法思路
    1. 给数组排序
    2. 遍历数组,从0遍历到小于length-2防止越界
    3. 如果当前的数字等于前一个数字,则跳过这个数,去掉重复
    4. 如果数字不同,则设置start= i+1end=length-1,查看istartend三个数的和此零大还是小,如果比0小,start++,如果比0大,end--,如果等于0,把这三个数加入到结果里。
    5. 返回结果
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
29
30
31
32
33
34
35
36
37
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const result = []; //存放结果
nums.sort(function (a, b) { //数组排序
return a - b;
});

for (let i = 0; i < nums.length - 2; i++) { //遍历数组至length-2,防止越界
if (i === 0 || nums[i] !== nums[i - 1]) { //去重操作,重复就跳过
let start = i + 1;
let end = nums.length - 1;
while (start < end) { //两边指针向里面缩
if (nums[i] + nums[start] + nums[end] === 0) { //找到正确结果
result.push([nums[i], nums[start], nums[end]]); //存放到result数组里
start++;
end--;
//去重操作
while (start < end && nums[start] === nums[start - 1]) {
start++;
}
while (start < end && nums[end] === nums[end + 1]) {
end--;
}
} else if (nums[i] + nums[start] + nums[end] < 0) {
start++;
} else {
end--;
}
}
}
}

return result;
};