[LeetCode#1] Two Sum

2024. 7. 22. 17:37·Algorithm/문제풀이


❒ Description


  • 제목 : Two Sum
  • 링크 : https://leetcode.com/problems/two-sum/description/
  • 카테고리 : 선형 자료구조 중 배열 문제에 속한다.

주어진 배열 중 2개의 요소의 합이 target이 될 때, 각 요소의 index를 return하는 문제

 

 

 

❒ Solution


 

1. Brute Force

public static int[] solve1(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}
  • 시간 복잡도 : O(n²)
  • 모든 경우를 전부 확인하는 방법

 

2. Two-pass Hash Table

▶︎ Two-pass Hash Table
주로 두 번의 탐색을 통해 문제를 해결하는 알고리즘에서 사용되는 접근 방식이다.
이 기법은 특히 배열에서 특정 조건을 만족하는 두 요소를 찾는 문제에서 유용하다.
예를 들어, 배열에서 두 수의 합이 특정 값이 되는 두 요소를 찾는 문제에서 자주 사용된다.
public static int[] solve2(int[] nums, int target) {
    Map<Integer, Integer> numsMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        numsMap.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        if (numsMap.containsKey(target - nums[i]) && i != numsMap.get(target - nums[i])) {
            return new int[]{i, numsMap.get(target-nums[i])};
        }
    }
    return new int[]{};
}
  • 시간 복잡도 : O(n)
  • Map 자료구조에 주어진 배열을 담고, 뺄샘으로 결과를 도출하는 방법
i != numsMap.get(target - nums[i])

위 코드가 필요한 이유는 이렇다. 예를 들어 배열이 [3,2,4] 이고 target이 6인 경우 numsMap.get(3)은

0이 되고, 이렇게 되면 [0,0]이 마치 정답인 것처럼 착각할 수 있기 때문에 넣은 코드이다.

 


3. One-pass Hash Table

public int[] solve3(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    int n = nums.length;

    for (int i = 0; i < n; i++) {
        int complement = target - nums[i];
        if (numMap.containsKey(complement)) {
            return new int[]{numMap.get(complement), i};
        }
        numMap.put(nums[i], i);
    }
    return new int[]{};
}
  • 시간 복잡도 : O(n)
  • 주어진 배열을 순회하면서 Map 자료구조에 배열의 요소를 담는 방식

 

'Algorithm > 문제풀이' 카테고리의 다른 글

[LeetCode#234] Palindrome Linked List  (0) 2024.07.24
[LeetCode#121] Best Time to Buy and Sell Stock  (0) 2024.07.24
[LeetCode#238] Product of Array Except Self  (0) 2024.07.23
[LeetCode#15] 3Sum  (0) 2024.07.23
[LeetCode#42] Trapping Rain Water  (0) 2024.07.23
'Algorithm/문제풀이' 카테고리의 다른 글
  • [LeetCode#121] Best Time to Buy and Sell Stock
  • [LeetCode#238] Product of Array Except Self
  • [LeetCode#15] 3Sum
  • [LeetCode#42] Trapping Rain Water
gilbert9172
gilbert9172
gilbert9172 님의 블로그 입니다.
  • gilbert9172
    バックエンド
    gilbert9172
  • 전체
    오늘
    어제
    • All Categories (173)
      • 우테코 7기 (21)
        • 1주차 (8)
        • 2주차 (5)
        • 3주차 (6)
      • Langauge (4)
        • Java (3)
        • Kotlin (1)
      • Back-End (13)
        • SpringBoot (1)
        • Trouble Shooting (0)
        • Setup & Configuration (1)
        • SQL (3)
        • Redis (8)
      • Architecture (6)
        • Multi Module (1)
        • DDD (5)
      • CS (30)
        • Data Structure (6)
        • Operating System (0)
        • Network (12)
        • Database (10)
        • Design Pattern (2)
      • Algorithm (78)
        • 내용 정리 (18)
        • 문제풀이 (60)
      • DevOps (6)
        • AWS (5)
        • Git (1)
      • Front-End (1)
        • Trouble Shooting (1)
      • Project (6)
        • 페이스콕 (6)
      • Book (7)
        • 이벤트 기반 마이크로서비스 구축 (6)
        • 친절한 SQL 튜닝 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    오블완
    greedy
    Back-Tracking
    Two-Pointer
    부분단조성
    sliding-window
    binarysearch
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.2
gilbert9172
[LeetCode#1] Two Sum
상단으로

티스토리툴바