[Leetcode] 1. Two Sum 문제 풀이

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

Two Sum - LeetCode

문제 내용

2개를 더해서 target 되는 index를 구하는 문제

 

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: Because nums[0] + nums[1] == 9, we return [0, 1].

 

문제 풀이

일반적으로 하면 O(n^2) 만큼 걸린다.

2개의 값을 더하는 것은 하나를 target에서 빼면 1개 요소만 찾는 문제가 된다.

1개 값 찾는 문제는 바이너리 서치를 이용하면 정렬되어 있을때 logn 만에 가능하다.

 

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> values(nums.begin(), nums.end());
        sort(values.begin(), values.end());
        
        int a, b;
        for (int i = values.size()-1; i > 0; --i) {
            int j = lower_bound(values.begin(), values.end(), target-values[i]) - values.begin();
            if (target == values[i] + values[j]) {
                a = values[i];
                b = values[j];
                break;
            }
        }
        
        vector<int> ans;
        for (int i = 0; i < nums.size(); ++i) {
            if (a == nums[i])
                ans.push_back(i);
            else if (b == nums[i])
                ans.push_back(i);
        }
        return ans;
    }
};