competitive-programming2021년 11월 1일1분 분량

[LeetCode] 1. Two Sum 풀이

수정일: 2021년 11월 1일

Two pointers

지원 언어:enko

#Problem

1. Two Sum

#Approach

meet in the middle.

답이되는 index 두개를 $l, r$ 이라고 했을 때 $arr[l] = target - arr[r]$ .
$l$ 은 왼쪽에서 부터, $r$ 은 오른쪽에서부터 순회하면서 두 값의 합을 관찰해보면, $l$ 일때 너무 커서 감소시켰던 $r$ 값은 $l+1$ 이 되었을 때 다시 확인할 필요가 없다.

#Code

/**
 * author: jooncco
 * written: 2021. 11. 01. Mon. 23:34:56 [UTC+9]
 **/

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

class Solution {
public:
    vi twoSum(vi& nums, int target) {
        int n= nums.size();
        vii arr;
        for (int i=0; i < n; ++i)
            arr.push_back({nums[i],i});

        sort(arr.begin(), arr.end());
        int l= 0, r= n-1;
        while (l < r) {
            while (arr[l].first+arr[r].first > target) --r;
            if (arr[l].first+arr[r].first == target) {
                int lIdx= min(arr[l].second, arr[r].second);
                int rIdx= max(arr[l].second, arr[r].second);
                return {lIdx, rIdx};
            }
            ++l;
        }
        return {0,0};
    }
};

#Complexity

Time: $O(n)$
Space: $O(n)$