LeetCode167. Two Sum II - Input array is sorted（思维）

Easy
Accepted：203,351
Submissions：416,166

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

Example

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

链接

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

题意

给定一个升序数组，找到两个元素使得它们的和等于target，返回这两个元素的下标（从1开始）。保证答案唯一且同一个元素最多只能使用一次。

之前也有一个题目，差不多一样：LeetCode1. Two Sum（思维）。

题解

暴力解法就不说了。
题目说了有序，所以可以使用二分查找，对于一个数a[i]，找另一个数target-a[i]是否在这个数组中，两个数的下标不同，使用二分会有一个问题，如果出现{2, 3, 3} 6这种情况，二分找到的数target-a[i]的下标和a[i]的下标相同，所以需要分类讨论下，看是否存在重复元素。时间复杂度$O(nlogn)$。
还有一种解决方法就是用unordered_map来存元素和下标间的映射关系，常数时间查询，但是注意有一个隐藏的bug，当出现相同的元素时会保留后面一个元素的键值关系，但是因为从前往后遍历且答案唯一所以能AC。

代码

Runtime: 4 ms, faster than 99.00% of C++ online submissions for Two Sum II - Input array is sorted.
Memory Usage: 1.6 MB, less than 66.67% of C++ online submissions for Two Sum II - Input array is sorted.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int len = numbers.size();
        vector <int> ans;
        for (int i = 0; i < len; ++i)
        {
            int x = target - numbers[i];
            int pos = binarySearch(numbers, x);
            if (pos != -1)
            {
                // 存在数值相同元素
                if (pos == i && i < len - 1 && numbers[i] == numbers[i + 1])  
                {
                    ans.push_back(i + 1);
                    ans.push_back(i + 2);
                }
                else if (pos != i)
                {
                    ans.push_back(i + 1);
                    ans.push_back(pos + 1);
                }
                break;
            }
        }
        return ans;
    }
    
    // 二分查找
    int binarySearch(vector<int>& numbers, int x)
    {
        int l = 0, r = numbers.size(), m;
        while (l <= r)
        {
            m = l + (r - l) / 2;
            if (x == numbers[m])
                return m;
            if (x > numbers[m])
                l = m + 1;
            else
                r = m - 1;
        }
        return -1;
    }
};

//     Accepted    4 ms    1.6 MB

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> ump;
        vector <int> ans;
        int len = nums.size(), tmp;
        for (int i = 0; i < len; ++i) // 建立映射关系
            ump[nums[i]] = i;
        for (int i = 0; i < len; ++i)
        {
            tmp = target - nums[i];
            if (ump.count(tmp) && ump[tmp] != i) // 存在target-a[i]且不为同一个数
            {
                ans.push_back(i + 1);
                ans.push_back(ump[tmp] + 1);
                break;
            }
        }
        return ans;
    }
};

拓展

还有一种$O(n)$的解法，使用对撞指针l，r，l和r初始化指向数组两端，如果nums[l] + nums[r] == target，那么直接返回，如果大于就让r--，小于就让l++，充分利用数组的有序性。

// Accepted    4 ms 1.6 MB
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int len = numbers.size();
        vector <int> ans;
        int l = 0, r = len - 1;
        while (l < r)
        {
            if (numbers[l] + numbers[r] == target)
            {
                ans.push_back(l + 1);
                ans.push_back(r + 1);
                break;
            }
            else if (numbers[l] + numbers[r] < target)
                l++;
            else if (numbers[l] + numbers[r] > target)
                r--;
        }
        return ans;
        // throw invalid_argument("No solution.")
    }
};

The end.
2019年2月3日星期日