LeetCode) 1. Two Sum

배열을 순회하면서 배열 인자의 합이 target이 되는 인덱스를 구하는 문제.

O(n^2)보다 적은 시간복잡도를 원한다는 문구가 있었기에, map을 사용했다.
배열을 순회하면서 target - nums[i]를 하게 되면, 필요한 숫자가 나오고 그 값이 hashMap에 존재하는지를 확인했다. 유효한 값은 하나만 존재한다고 명시되어 있으므로 그 값을 바로 리턴해주면 된다. 만약 값이 없으면 배열의 값을 키로, 인덱스를 value로 가지는 요소로 넣어주면 O(n)의 시간복잡도를 가지게 된다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        Map<Integer,Integer> valueMap = new HashMap<>();

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

            if(valueMap.containsKey(needValue)){
                return new int[]{valueMap.get(needValue),i};
            }else{
                valueMap.put(nums[i],i);
            }
        }

        return new int[]{-1,-1};
    }
}