哈希表

594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1

给你一个整数数组 nums ,请你在所有可能的

子序列

中找到最长的和谐子序列的长度。

数组的 子序列 是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number[]} nums
* @return {number}
*/
var findLHS = function(nums) {
let newmap = new Map()
for(let i=0;i<nums.length;i++){
if(newmap.has(nums[i])){
newmap.set(nums[i],newmap.get(nums[i])+1)
}else{
newmap.set(nums[i],1)
}
}
let maxnumber = 0
for(const app of newmap.keys()) {
if(newmap.has(app+1)){
maxnumber = Math.max(maxnumber,newmap.get(app)+newmap.get(app+1))
}
}
return maxnumber
};
1
2
3
4
5
6
7
8
9
10
11
12
13
func findLHS(nums []int) int {
numsmap := make(map[int]int)
for _, value := range nums {
numsmap[value]++
}
ansnumber := 0
for key, valuenumber := range numsmap {
if numsmap[key+1] > 0 && valuenumber+numsmap[key+1] > ansnumber {
ansnumber = valuenumber + numsmap[key+1]
}
}
return ansnumber
}

1897. 重新分配字符使所有字符串都相等

给你一个字符串数组 words(下标 从 0 开始 计数)。

在一步操作中,需先选出两个 不同 下标 ij,其中 words[i] 是一个非空字符串,接着将 words[i] 中的 任一 字符移动到 words[j] 中的 任一 位置上。

如果执行任意步操作可以使 words 中的每个字符串都相等,返回 true ;否则,返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {string[]} words
* @return {boolean}
*/
var makeEqual = function (words) {
let map = new Map()
for (let i = 0; i < words.length; i++) {
for (let j = 0; j < words[i].length; j++) {
if (map.has(words[i][j])) {
map.set(words[i][j], map.get(words[i][j])+1)
} else {
map.set(words[i][j], 1)
}
}
}
for (const value of map.values()) {
if (value % words.length !== 0) {
return false
}
}
return true
};

两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

思路:1.暴力解法 2.哈希表加上JavaScript的map的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// 写法一
var twoSum = function(nums, target) {
let map = new Map()
let length = nums.length
for(let i=0;i<length;i++) {
if(map.has(target-nums[i])) {
return [map.get(target-nums[i]),i]
} else {
map.set(nums[i],i)
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
// 写法二
var twoSum = function(nums, target) {
let map = new Map()
let length = nums.length;
for(let i=0;i<length;i++) {
let number = nums[i]
let pre = map[target - number]
if(pre !== undefined) {
return [pre,i]
}
map[number] = i
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 写法三
// 类似于哈希表的写法,采用的是对象的方法
var twoSum = function(nums, target) {
const prearray = {}
for(let i=0;i<nums.length;i++) {
const current = nums[i];
const targetnumber = target - current
const targetindex = prearray[targetnumber]
if(targetindex !== undefined) {
return [targetindex,i]
}else{
prearray[current] = i
}
}
};