Problem


Key Idea

meet in the middle.

  • λ‹΅μ΄λ˜λŠ” index λ‘κ°œλ₯Ό \(l, r\) 이라고 ν–ˆμ„ λ•Œ \(arr[l] = target - arr[r]\).
  • \(l\)은 μ™Όμͺ½μ—μ„œ λΆ€ν„°, \(r\)은 였λ₯Έμͺ½μ—μ„œλΆ€ν„° μˆœνšŒν•˜λ©΄μ„œ 두 κ°’μ˜ 합을 관찰해보면, \(l\)μΌλ•Œ λ„ˆλ¬΄ μ»€μ„œ κ°μ†Œμ‹œμΌ°λ˜ \(r\)값은 \(l+1\)이 λ˜μ—ˆμ„ λ•Œ λ‹€μ‹œ 확인할 ν•„μš”κ°€ μ—†λ‹€.

  • Time: \(O(n)\)


Implementation

/**
 * 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};
    }
};

Leave a comment