[Easy] LeetCode - no.1 Two Sum : Java

https://leetcode.com/problems/two-sum/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

int 배열 nums 내의 2개의 숫자를 더했을 경우 target이 된다면, 각각의 인덱스를 int 배열로 반환

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

 

 

 

풀이1

  public static int[] twoSum(int[] nums, int target) {
    int[] answer = new int[2];

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

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

    }

    return answer;
  }

• 이중 for문 사용
• nums[i]를 특정하고, 인덱스 i 이후의 값들 중 nums[i]와 더했을 때 target이 되는 경우를 찾음
  • 찾았을 경우 : answer[0] = i, answer[1] = j
• 시간복잡도 : O(N²)

 

 

풀이2

  public static int[] twoSum2(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
      int remain = target - nums[i];

      if (map.containsKey(remain)) {
        return new int[]{map.get(remain), i};
      }

      map.put(nums[i], i);
    }

    return new int[]{};
  }

• HashMap 사용
  • key : 숫자, value : 인덱스 값
• target에서 nums[i] (현재 인덱스의 값)을 뺀 remain 계산
  • map에 remain이 key값으로 존재한다면 map.get(remain)과 i를 반환
  • 없다면 map.put(nums[i], i)
• 시간복잡도 : O(N)