js两数之和

两数之和

两层for循环

// O(n^2)
const twoNum = function(nums,target){
  for(let i =0;i<nums.length;i++){
    for(let j=i+1 ;j<nums.length;j++){
      if(nums[i]+nums[j]===target){
        return[i,j]
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10

双指针

// 当数组为有序的时候O(n)
const twoNum2 = function(nums,target){
  let i = 0 // 头
  let j = nums.length-1 // 尾
  while (i<j){
    const sum = nums[i]+nums[j]
    if(sum>target){
      j--
    }else if(sum<target){
      i++
    }else{
      return [i,j]
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

js的map和set

Map

是一组键值对的结构，具有极快的查找速度。

var m = new Map([['Michael', 95], ['Bob', 75], ['Tracy', 85]]);
m.get('Michael'); // 95
1
2

初始化Map需要一个二维数组，或者直接初始化一个空Map。Map具有以下方法：

var m = new Map(); // 空Map
m.set('Adam', 67); // 添加新的key-value
m.has('Adam'); // 是否存在key 'Adam': true
m.get('Adam'); // 67
m.delete('Adam'); // 删除key 'Adam'
m.get('Adam'); // undefined
1
2
3
4
5
6

• clear从映射中移除所有元素。
• delete从映射中移除指定的元素。
• forEach对映射中的每个元素执行指定操作。
• get返回映射中的指定元素。
• has如果映射包含指定元素，则返回 true。
• set添加一个新建元素到映射。
• toString返回映射的字符串表示形式。
• valueOf返回指定对象的原始值。

Set

Set是一种叫做集合的数据结构，也是一组key的集合，但不存储value。由于key不能重复，所以，在Set中，没有重复的key。

要创建一个Set，需要提供一个Array作为输入，或者直接创建一个空Set

var s1 = new Set(); // 空Set
var s2 = new Set([1, 2, 3]); // 含1, 2, 3
1
2

Set的属性：

• size：返回集合所包含元素的数量

Set的方法：

操作方法

• add(value)：向集合添加一个新的项
• delete(value)：从集合中移除一个值
• has(value)：如果值在集合中存在，返回true,否则false
• clear(): 移除集合里所有的项

遍历方法

• keys()：返回一个包含集合中所有键的数组
• values()：返回一个包含集合中所有值的数组
• entries：返回一个包含集合中所有键值对的数组
• forEach()：用于对集合成员执行某种操作，没有返回值