LeetCode/solutions/167. Two Sum II - Input array is sorted.md

167. Two Sum II - Input array is sorted

思路

思路一

先遍历一遍numbers用一个map记录每个元素的下标(从1开始)，然后遍历一遍查看mp[target - numbers[i]]是否不为0，是则找到。
仔细观察可知两个循环可以合并在一起，但是要注意是先判断再用map记录，否则假如target刚好是某个元素的两倍的话就会返回两个同样的下标。 map查找的复杂度为O(logn),所以总的时间复杂度O(nlogn), 空间复杂度O(n)

思路二

思路一没有运用到数组已经排序的这一信息，复杂度较高。
同时从首尾向中间遍历，若元素和大于target，则尾指针前移；若元素和小于target，首指针前移。
此时时间复杂度O(n), 空间复杂度O(1).

C++

思路一

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        map<int, int>mp;
        vector<int>result;
        for(int i = 0; i < numbers.size(); i++) {
            if(mp[target - numbers[i]] != 0){
                result.push_back(mp[target - numbers[i]]);
                result.push_back(i + 1);
                return result;
            }
            mp[numbers[i]] = i + 1;
        }     
    }
};

思路二

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0, high = numbers.size() - 1;
        while(1){
            if(numbers[low] + numbers[high] == target) 
                return vector<int>({low+1, high+1});
            else if(numbers[low] + numbers[high] < target)
                low++;
            else 
                high--;
        }
    }
};