[Easy] 1. Two Sum

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]

Leetcode 1번 문제 Two Sum에서는 하나의 배열과 하나의 target value 가 주어지며, 배열에서 두 개의 값을 더했을때 target value와 같아지는 index를 가지고있는 배열을 반환하는 문제이다. 

 

#Brute force 방식 O(n^2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int arr[] = new int[2];
            for(int i = 0; i < nums.length;i++){
                for(int j = i+1; j < nums.length;j++){
                if(nums[i] + nums[j] == target){
                    arr[0] = i;
                    arr[1] = j;
                 }    
               }
            }
        return arr;
    }
}

 

#HashMap 방식 O(n)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> indexMap = new HashMap<Integer,Integer>();
        for(int i = 0; i < numbers.length; i++){
            int requiredNum = target - numbers[i];
            if(indexMap.containsKey(requiredNum)){
                int[] toReturn = {indexMap.get(requiredNum), i};
                return toReturn;
            }
            indexMap.put(numbers[i], i);
        }
        return null;
    }
}