FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/code/lc923.java at master · mJackie/leetcode · GitHub
mJackie
/
leetcode
Public
Notifications
You must be signed in to change notification settings
Fork
135
Star
405
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
code
/
lc923.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
56 lines (54 loc) · 2.02 KB
Breadcrumbs
leetcode
/
code
/
lc923.java
Copy path
File metadata and controls
56 lines (54 loc) · 2.02 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package
code
;
import
java
.
util
.
Arrays
;
import
java
.
util
.
HashMap
;
/*
* 923. 3Sum With Multiplicity
* 题意：3Sum有几种？数组中有重复数字
* 难度：Medium
* 分类：Two Pointers
* 思路：由于本题只要求给出多少种Int值，所以不一定非要用3Sum的思路，有很多更简答的方法
* 3种思路
* Tips：lc15, lc16, lc923
*/
public
class
lc923
{
public
int
threeSumMulti
(
int
[]
A
,
int
target
) {
int
res
=
0
;
HashMap
<
Integer
,
Integer
>
hm
=
new
HashMap
();
for
(
int
i
=
0
;
i
<
A
.
length
;
i
++) {
res
= (
res
+
hm
.
getOrDefault
(
target
-
A
[
i
],
0
))%
1000000007
;
// i之前的数字，两个组合起来，是否 == target-A[i]
for
(
int
j
=
0
;
j
<
i
;
j
++) {
hm
.
put
(
A
[
i
]+
A
[
j
],
hm
.
getOrDefault
(
A
[
i
]+
A
[
j
],
0
)+
1
);
}
}
return
res
;
}
public
int
threeSumMulti2
(
int
[]
A
,
int
target
) {
//3Sum的思路
int
res
=
0
;
Arrays
.
sort
(
A
);
for
(
int
i
=
0
;
i
<
A
.
length
-
2
;
i
++) {
int
left
=
i
+
1
,
right
=
A
.
length
-
1
;
while
(
left
<
right
){
if
(
A
[
i
]+
A
[
left
]+
A
[
right
]<
target
)
left
++;
else
if
(
A
[
i
]+
A
[
left
]+
A
[
right
]>
target
)
right
--;
else
if
(
A
[
left
]==
A
[
right
]) {
//如果相等，则直接 C N 取 2，计算出来，然后break
res
= (
res
+ (
right
-
left
)*(
right
-
left
+
1
)/
2
)%
1000000007
;
break
;
//不用继续移动指针了
}
else
{
int
leftcount
=
1
,
rightcount
=
1
;
while
(
A
[
left
]==
A
[
left
+
1
]) {
left
++;
leftcount
++;
}
while
(
A
[
right
]==
A
[
right
-
1
]) {
right
--;
rightcount
++;
}
res
= (
res
+
leftcount
*
rightcount
)%
1000000007
;
left
++;
//别忘了，最后还要操作一下
right
--;
}
}
}
return
res
;
}
}
Back
|
FazBrowse Home
|
New Git URL