[leetCode 1번] Two Sum (Java)

1.문제

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - The World's Leading Online Programming Learning Platform

---

2.문제설명

주어진 배열에서 두개의 값을 더했을 때 타겟값이 같으면 index의 위치를 반환하는 문제이다.

 

---

3.소스코드

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

4.소스코드 설명

 

주어진 배열을 순회하면서 자신보다 앞에 있는것들을 다 더해보면서 target 값이 맞는지 비교하는 브루투포스 형식으로 풀었다.

 

---

5.회고

 

 

이문제는 간단하게 부루트포스로 풀어도 충분히 속도와 메모리측면에서 괜찮을 것이라고 생각 하였지만.  메모리에서는 90%이상의 좋은 효율을 보엿지만 메모리 측면에서는 역시...O(N^2) 은 느리다라는 것을 알았다.

 

HashTable 을 활용하여 속도를 개선 해 보았다.! 

 

HashMap 은 읽기에 특화되어있어 역시나 속도 가 43 -> 1 까지 빨라졌다.

 

HashMap 에 추가하며 이 hashMap에 키가 존재하는지에 여부를 따져 계산값을 찾아 return 해주는 식으로 변경하였다.