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.

Example 1 : 

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].


Example 2: 
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.	

🍊 맨 처음 내가 짠 코드.

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= 1; j< nums.length; j++) { 
                if( nums[i] + nums[j] == target && i !=j) {
                    result[0]=i;    
                    result[1] =j;  
                      
                }
                
            }
        }   return result;
    }
}

Runtime 99 ms

O(n2) 만큼의 시간이 걸린다.
효율적으로 시간을 줄이는 게 중요하다.

🍊 2번째로 짠 코드(List 이용)

public static int[] twoSum(int[] nums, int target) {

		// [2,7,6,9] target = 9

		List<Integer> restOfTarget = new ArrayList<Integer>();

		int numSize = nums.length;

		for (int i = 0; i < numSize; i++) {

			int temp = target - nums[i];

			if (restOfTarget.contains(temp)) {

				return new int[] { restOfTarget.indexOf(temp), i };

			} else {
				restOfTarget.add(i, nums[i]);

			}
		}
		return new int[2];

	}

Runtime 275 ms

🍊 마지막으로 짠 코드(HashTable 이용)

HashTable은 검색하는 시간이 O(n)이다.

public class twoSumUsingHashMap {

public static int[] twoSumUsingHashMap(int[] nums, int target) {

	HashMap<Integer, Integer> restOfTarget = new HashMap<Integer, Integer>();

	for (int i = 0; i < nums.length; i++) {

		if (restOfTarget.containsKey(target - nums[i])) {

			return new int[] { restOfTarget.get(target - nums[i]), i };

		} else {
			restOfTarget.put(nums[i], i);
		}

	}

	return new int[2];

	} 
}

Runtime 4 ms

🍏 코드를 짜면서...

막막하나 재밌다.
처음에는 컬렉션을 자바 컬렉션 이론공부때 빼곤 ArrayList나 HashTable, HashMap 그 어느 것도 써본 적이 없다. 포트폴리오 만드면서 List나 써봤지...
다중 for문을 써서 어찌어찌 승인되었는데 다른 사람들의 솔루션을 확인해보니 벡터, 헤쉬맵, 어레이리스트 등등을 이용해 문제를 해결하는 것을 보아 막막했다.
애초에 코테를 준비해본적도 너무 게을러서 국비시절 시 남들이 열심히 백준문제를 풀 때 난 여유로웠다. (도대체 무슨 근자감이었던 게야...)
도대체 어떻게 leetCode를 활용할 지 고민하다 개발바닥 단톡방에 공부방법을 물었더니 뻔한 소리를 했다.

?? : "지금 해시테이블이 뭔지 보신거잖아요 ㅋ 더 궁금하면 자료를 찾아보면되겠죵? 활용법은 이미보셨으니까"

나 : 아 네네 감사합니다.

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
ㅋㅋㅋ

그 외에 나동빈의 "이것이 코딩테스트다" 유튜브 추천, 코딩테스트 시작 전에 준비해야할 것들을 미리 공부해보라며 조언받았다.

막막한 상태에서 하소연하는 것처럼 질문을 해서.. 보는 사람들 답답했을 듯 .

바로 해당 컬랙션을 공부해보고 , 유튜브에 나와있는 풀이, 다른 사람들이 쓴 코드등을 공부하면서 직접 코드를 짜보았다.
깃헙에도 올리고, 블로그에도 올리고, 릿코드도 출석하고 나름 열심히 한 거 같다.
근데 사실 아직도 시간복잡도, 공간복잡도 등등 모르는 개념들이 있어서 여전히 어리둥절하다.

공부하다 보면 점차 아는 것도 많아질테니 너무 겁내지 않도록 한다.

나의 첫 코테 도전기 포스팅 완료!