https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
Solution 1. Use two pointers to search the array
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res;
for(int i=0,j=numbers.size()-1;i<j;) {
if(numbers[i]+numbers[j] == target) {
res={i+1,j+1};
break;
}
else if(numbers[i]+numbers[j] < target) i++;
else j--;
}
return res;
}
Solution 2. Construct a map from value to its index
vector<int> twoSum(vector<int>& numbers, int target) {
unordered_map<int,int> m;
for(int i=0; i<numbers.size();i++) {
if(m.find(target-numbers[i])!=m.end())
return vector<int> {m[target-numbers[i]]+1,i+1};
m[numbers[i]] = i;
}
}
No comments:
Post a Comment