문제

https://leetcode.com/problems/two-sum/

• 주어진 리스트에서 두 수의 합이 target인 쌍을 구하는 문제

풀이

완전 탐색으로 접근을 했다가 효율성에서 좋지 못하다고 판단하여 해시맵을 활용하여 문제를 풀이했다.

class Solution {
  List<int> twoSum(List<int> nums, int target) {
    Map<int,int> hash = {};
    var rst = [0,0];
    for(var i = 0; i<nums.length; i++){
        hash[nums[i]] = i;
    }
    for (var j = 0; j<nums.length; j++){
        var diff = target - nums[j];
        if(hash.containsKey(diff)){
            if(hash[diff] == j){
                continue;
            } else {
                rst[0] = j;
                rst[1] = hash[diff]!;
                break;
            }
        }
    }
    return rst;
  }
}

첫번째 for문에서 리스트를 돌며 hash에 값 : 인덱스의 형태로 저장한다.

두번째 for문에서 리스트의 아이템을 순차적으로 돌며 target 값에서 각 아이템을 뺀 값이 hash에 존재하는지 체크한다. hash에 존재하는 경우, 만약 해당 키에 대한 값이 for문 내 현재 인덱스와 동일한 경우를 제외시킨다.