Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 버블정렬
- 재귀와반복문
- 백준 11659
- 투포인터알고리즘
- Spring MVC 동작원리
- OOP
- String.valueOf()
- GCP
- Spring MVC 구성요소
- vm인스턴스생성
- List.of
- 코드스테이츠
- 구간합구하기
- 프로그래머스
- 코딩테스트
- Array.asList
- 알고리즘
- 재귀함수
- 성능테스트툴
- 11659
- 인텔리제이
- MySQL
- 백준
- java
- 자바
- 싱글톤패턴
- 코드스테이츠 백엔드
- 클라우드에서 도커 실행하기
- Spring Web MVC
- 스택
Archives
- Today
- Total
순간을 기록으로
[LeetCode] Two Sum 본문
문제
풀이 1: 완저탐색
완전탐색으로 문제를 풀 수 있지만 효율적이지 못하다.
데이터의 크기는 10000이고 완전탐색의 경우 O(n^2)이므로 아슬아슬하게 통과한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i=0; i<nums.length; i++) {
for (int j=i+1; j<nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return null;
}
}
|
cs |
풀이2: Hash Table 이용하기
해시맵을 사용하면 for문을 한번만 사용하기 때문에 O(N)으로 시간복잡도를 낮출 수 있다.
hash table에서 데이터 조회는 O(1)의 시간을 갖는다.
해시맵을 이용하여 요소값과 인덱스를 매핑하여 저장할 수 있다.
따라서 한 번만 순회하면서 두 요소의 합이 target값이 되는 경우를 찾을 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[1] =map.get(target - nums[i]);
result[0] = i;
return result;
}
map.put(nums[i], i);
}
return result;
}
}
|
cs |
'Problem Solving' 카테고리의 다른 글
[LeetCode] Employees With Missing Information (0) | 2022.11.08 |
---|---|
[LeetCode] Rearrange Products Table (0) | 2022.11.08 |
[LeetCode] Patients With a Condition (0) | 2022.11.07 |
[LeetCode] Group Sold Products By The Date (0) | 2022.11.07 |
[LeetCode] Fix Names in a Table (0) | 2022.11.07 |
Comments