MENU

LeetCode167. Two Sum II - Input array is sorted(思维)

2019 年 02 月 03 日 • 阅读: 883 • LeetCode阅读设置

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日 星期日
最后编辑于: 2019 年 02 月 16 日