forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhaxr369.java
More file actions
64 lines (60 loc) ยท 2.03 KB
/
haxr369.java
File metadata and controls
64 lines (60 loc) ยท 2.03 KB
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
57
58
59
60
61
62
63
64
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* ์ธ ์์ ์ธ๋ฑ์ค๊ฐ ๋ชจ๋ ๋ค๋ฅด๊ณ ์ธ ์ ํฉ์ด 0์ธ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๊ธฐ
* ์ธ ์ซ์๊ฐ ๋ค์ด๊ฐ ๋ฐฐ์ด์ ์ค๋ณต๋๊ฒ ํ์ง ์์๋ค.
*
* 1. ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ค. => O(N^3)
* 3000*3000*3000 == 9*10^9 => 9์ต๊ฑด...
* 2. left, mid, right๋ผ๊ณ ํ ๋, mid๋ฅผ ๊ณ ์ ํ๊ณ left, right๋ง ์์ง์ด๋ two pointer๋ฅผ ์์ฉํ๊ธฐ
*/
class Solution {
/**
* Runtime: 545 ms (Beats 14.44%)
* Memory: 60.78 MB (Beats 5.38%)
* Space Complexity: O(N)
* - ์ ๋ ฌ์ ์ํ ๊ณต๊ฐ => O(N)
* - ์ธ ์๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ๋ฆฌ์คํธ => O(3)
* > O(N) + O(3) => O(N)
* Time Complexity: O(NlogN)
* - ์ ๋ ฌ์ ์ํ ์๊ฐ => O(NlogN)
* - mid์ ์ํ => O(N)
* - two pointer ์กฐํ => O(N)
* > O(NlogN) + O(N)*O(N) ~= O(N^2)
*/
public List<List<Integer>> threeSum(int[] nums) {
int L = nums.length;
Arrays.sort(nums);
Set<List<Integer>> st = new HashSet<>();
// mid๋ฅผ ๋๋ ค๊ฐ๋ฉด์ ํฌ ํฌ์ธํฐ ์งํ
for (int mid = 1; mid < L - 1; mid++) {
int left = 0;
int right = L - 1;
while (left < mid && mid < right) {
int sm = nums[left] + nums[mid] + nums[right];
if (sm == 0) {
/**
* left๋ฅผ ๋ํ๋ ์ด์ :
* ํ์ฌ ์ฐพ์ ๊ฒฝ์ฐ์ ์ ์ธ์ ๋ค๋ฅธ ๊ฒฝ์ฐ๊ฐ ์กด์ฌํ ์ ์์
* ex) -7,1,6 / -6,1,5
* => mid๋ ๊ณ ์ ์ด์ง๋ง, left๋ ๋๋ฆฌ๊ณ right๋ฅผ ์ค์ฌ์ 0์ ๋ง๋ค ์ ์๋ ๋ค๋ฅธ ๊ฒฝ์ฐ๊ฐ ์์
*/
List<Integer> li = new ArrayList<>();
li.add(nums[left]);
li.add(nums[mid]);
li.add(nums[right]);
st.add(li); // ์ค๋ณต๊ฐ์ด ์์ด๋ ๋ฌด์ํ ์ ์์.
left++;
} else if (sm < 0) { // ๋ถ์กฑํ๋ฉด left ๋๋ฆฌ๊ธฐ
left++;
} else { // ๊ณผํ๋ฉด right ์ค์ด๊ธฐ
right--;
}
}
}
return new ArrayList<>(st);
}
}