1. 两数之和
找数组内，两个元素值的和=target的数的下标
用
Map
来存遍历过的
key: 元素值``value: 下标
，遍历数组，计算它和
target
的差，找
Map
中有没有：
有：返回下标
没有：加入
Map
中继续找
失散的母子们：一群人中有几对母子，警察一个一个问他们要找的谁，用一张表存每个人的信息和要找的人，首先看表里有没有要找的那个人，如果没有就把他要找的人和信息记下来，看后面会不会有人找
用
map
映射
*
@param
{
number[]
}
nums
*
@param
{
number
}
target
*
@return
{
number[]
}
var
twoSum =
function
(
nums, target
) {
let
map =
new
Map
()
for
(
let
i =
0
; i < nums.
length
; i++) {
let
sub = target - nums[i]
if
(map.
has
(sub))
return
[map.
get
(sub), i]
else
{
map.
set
(nums[i], i)
return
[]
454. 四数相加 II
454. 四数相加 II
四个
独立
的数组，求有几个A[i] + B[j] + C[k] + D[l] = 0，即
a + b + c + d = 0
定义一个
map
存
key: a+b，value: a+b出现过几次
遍历A和B，统计两数组元素之和，出现次数，存入
map
定义
count
，用来统计
a+b+c+d = 0
出现的次数
遍历C和D，
map
中找有
0-(c+d)
吗？有：
**count**
加上出现次数
用
Set
存
*
@param
{
number[]
}
nums1
*
@param
{
number[]
}
nums2
*
@param
{
number[]
}
nums3
*
@param
{
number[]
}
nums4
*
@return
{
number
}
var
fourSumCount =
function
(
nums1, nums2, nums3, nums4
) {
let
map =
new
Map
()
for
(
let
a
of
nums1) {
for
(
let
b
of
nums2) {
let
sum = a + b
map.
set
(sum, (map.
get
(sum) ||
0
) +
1
)
let
count =
0
for
(
let
c
of
nums3) {
for
(
let
d
of
nums4) {
let
sub =
0
- (c+d)
if
(map.
has
(sub))
count = count + map.
get
(sub)
return
count
383. 赎金信
383. 赎金信
后一个字符串中能找到前一个字符串中的所有元素
用数组映射
*
@param
{
string
}
ransomNote
*
@param
{
string
}
magazine
*
@return
{
boolean
}
var
canConstruct =
function
(
ransomNote, magazine
) {
let
hash =
new
Array
(
26
).
fill
(
0
)
let
base =
"a"
.
charCodeAt
()
for
(
let
i =
0
; i < ransomNote.
length
; i++) {
hash[ransomNote[i].
charCodeAt
() - base]++
for
(
let
j =
0
; j < magazine.
length
; j++) {
hash[magazine[j].
charCodeAt
() - base]--
for
(
let
h
of
hash) {
if
(h >
0
)
return
false
return
true
15. 三数之和
15. 三数之和
在一个数组内，找三个数的和为0，形成的不能重复的数组
用双指针解题：a + b + c = 0
首先对数组进行排序（小->大）
用
i
去遍历数组(a)，
l
从
i
下一个(b)，
r
从最后一个(c)，向中间移动找到合适的
可以用
-1 -1 0 0 1 1 3
判断去重
判断
去重
要找
与前一个是否相等
，相等说明这个数的已经处理过了，再处理也是一样的
重复
了
注意：不能先去重再找，会少一些情况：比如
[0, 0, 0]
就直接被删除了
三指针剪枝
*
@param
{
number[]
}
nums
*
@return
{
number[][]
}
var
threeSum =
function
(
nums
) {
nums.
sort
(
(
a, b
) =>
a-b)
let
result = [], conut =
0
for
(
let
i =
0
; i < nums.
length
; i++) {
if
(nums[i] >
0
)
break
if
(i >
0
&& nums[i] === nums[i-
1
])
continue
let
l = i +
1
let
r = nums.
length
-
1
while
(l < r) {
if
(nums[i] + nums[l] + nums[r] >
0
) r--
else
if
(nums[i] + nums[l] + nums[r] <
0
) l++
else
{
result[conut++] = [nums[i], nums[l], nums[r]]
while
(nums[l +
1
] === nums[l]) l++
while
(nums[r -
1
] === nums[r]) r--
l++
return
result
18. 四数之和
18. 四数之和
三数之和的升级版
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，一样是
l``r
移动找和满足
target
，五数之和、六数之和等等都采用这种解法
剪枝的时候要用
break
直接结束循环（后面都不看了），不能直接
return
，
nums[i] > target && nums[i] >=0
比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过，看
nums[i]
是否
>=0
，如果
>=0
，说明后面比它大的都是正数，加上正数只会越来越大
去重：与前一个相等，直接结束这次，继续下次循环
continue
（这个数不用看了）
排序：从小到大
遍历前面的值
剪枝，排除不满足的情况：已经大于
target
且
>=0
后面值越来越大、和前面相同：必须加上
>
起始值限制
i > k + 1、k > 0
l, r
分别从剩下的往中间遍历
四指针剪枝
*
@param
{
number[]
}
nums
*
@param
{
number
}
target
*
@return
{
number[][]
}
var
fourSum =
function
(
nums, target
) {
let
result = [], count =
0
nums.
sort
(
(
a, b
) =>
a - b)
for
(
let
k =
0
; k < nums.
length
; k++) {
if
(nums[k] > target && nums[k] >=
0
)
break
if
(k >
0
&& nums[k] === nums[k -
1
])
continue
for
(
let
i = k +
1
; i < nums.
length
; i++) {
let
l = i +
1
let
r = nums.
length
-
1
let
sum = nums[k] + nums[i]
if
(sum > target && sum >=
0
)
break
if
(i > k +
1
&& nums[i] === nums[i -
1
])
continue
while
(l < r) {
if
(sum + nums[l] + nums[r] > target) r--
else
if
(sum +nums[l] + nums[r] < target) l++
else
{
result[count++] = [nums[k], nums[i], nums[l], nums[r]]
while
(l < r && nums[l +
1
] === nums[l]) l++
while
(l < r && nums[r -
1
] === nums[r]) r--
return
result
