[LeetCode][java] #1 Two Sum

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

 

문제 

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

 

 

---

풀이

 

1. 하나의 값을 기준으로 모든 배열을 탐색하면서 값을 더해나간다.

2. 더해나가는 값들이 target 값 과 같아진다면 해당 i, j 값을 리턴한다.

3. 이중 for 문 -> 시간복잡도 O(n^2) => 매우 비효율적인 연산!

 

class Test {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = {0, 0};

        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    answer[0] = i;
                    answer[1] = j;
                }
            }
        }
        return answer;

    }

}
    
public class solution{
    public static void main(String[] args) {
        int[] nums = {2,7,11,15};
        int target = 9;
        Test test = new Test();
        int[] result = test.twoSum(nums, target);
        System.out.println(result[0] +","+ result[1]);
    }
}

 

 

효율적인 연산?? Hash Table 활용!! -> 검색하는 시간이 O(1)

 

◈ Hash Table 

키와 값을 1:1 형태로 가져가며 Hash Table 에 저장이 된다.

(키는 값을 식별하기 위한 고유한 키, 값은 키가 가진 값을 의미)

 

배열에 있는 데이터를 한번 쭈욱 돌면서 배열방의 값을 key 로, 인덱스를 value 로 해서 hash table에 담는다.

배열의 첫번째 방을 돌면서

 

9 - 2 = 7  -> 7을 key 가지는 방 찾아서 index 구함  => 1

9-7 = 2    -> 2을 key 가지는 방 찾아서 index 구함  => 0

9-11 = -2  -> -2을 key 가지는 방 찾아서 index 구함  => 없음

9-15 = -6  -> -6을 key 가지는 방 찾아서 index 구함  => 없음

 

import java.util.*;

// 더 효율적인 알고리즘 => Hash Table -> 검색하는 시간이 O(1)


class Test2 {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
            for (int j = 0; j < nums.length; j++) {
                Integer k = map.get(target - nums[j]);
                if (k != null && j != k)
                    return new int[]{j, k};
            }
        }
        return nums;
    }
}

public class sol2{
    public static void main(String[] args) {
        int[] nums = {2,7,11,15};
        int target = 9;

        Test2 test = new Test2();
        int[] result = test.twoSum(nums, target);
        System.out.println(result[0] +","+ result[1]);
    }
}