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