Wednesday, August 16, 2017

167. Two Sum II - Input array is sorted

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