Brute Force로 모든 경우에 대해 다 계산해도 답을 얻을 수 있지만 N^2은 너무 느리다. 그래서 어떻게 하면 시간복잡도를 줄일 수 있을까 고민해봤다. two pointer 같은걸 쓰면 O(N) 안에 해결할 수 있지 않을까 생각해봤는데, 연속된 합을 구하는 것도 아니기 때문에 잘못된 접근 방식이었다. 결국 힌트에 나와있는 해시맵을 사용해 차이값을 계산한 후, 그 값이 전에 나온 값이라면 리턴하고 아니면 해시맵에 넣어주는 방식으로 구현했다.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> umap;
int i = 0, size = nums.size();
for (i = 0; i < size; i++) {
int diff = target - nums[i];
auto it = umap.find(diff);
if (it != umap.end()) return { i, umap[diff] };
else umap[nums[i]] = i;
}
return {};
}
};