[ Array ] JAVA | 1. Two Sum (Medium)

< 리트코드 자바로 풀어보기 >

 

1번 Two Sum

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.

=> int[]인 배열 nums와 int target이 파라미터로 주어지며, nums 요소 중 두 요소의 합이 target과 동일할 때 두 숫자의 인덱스를 int[]인 배열로 반환하라. 정확히 딱 하나의 해결방법이 있으며 같은 요소는 두 번 사용할 수 없다.
이때 두 수의 인덱스의 순서는 상관없다.

+) 추가로 시간복잡도 O(n²) 보다 빠르도록 풀어보자.

 

Constraints:

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

 

예시 1)

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

 

예시 2)

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

 

예시 3)

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

 

---

 

< 내 풀이 >

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        for(int i = 0; i < nums.length-1; i++){ 
            for(int j = 1; j < nums.length; j++){ // 중첩 for문 = 시간복잡도 O(n²)
                if(i != j && nums[i] + nums[j] == target){
                    arr[0] = i;
                    arr[1] = j;
                }
            }
        }
        return arr;
    }
}

• Runtime : 94ms
• Memory : 44.1MB