1/167-两数之和

LeetCode

发布日期: 2021-05-29

LeetCode 1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

method: 哈希表

用map存储值和下标的映射，用unordered_map可以快一点

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hash;
    vector<int> res(2);
    for (int i = 0; i < nums.size(); ++i) {
        int x = target - nums[i];
        if (hash.find(x) != hash.end()) {   // 不能写成hash[x]，因为下标可能为0
            res[0] = i;
            res[1] = hash[x];
            return res;
        }
        hash[nums[i]] = i; // <nums[i],i>加入哈希表
    }
    return res;
}

时间复杂度：$O(n)$，需要遍历一次数组
空间复杂度：$O(n)$，主要为哈希表的开销

LeetCode 167. Two Sum II - Input array is sorted

LeetCode-167

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

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Example 1:

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

method 1: 双指针

sum < target, l++;
sum > target, r--;
sum == target, return;

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res(2);
    int l = 0, r = nums.size() - 1; 
    while (l < r) {
        int sum = nums[l] + nums[r];
        if (sum < target) l++;        // 小了
        else if (sum > target) r--;   // 大了
        else {
            res[0] = l + 1;
            res[1] = r + 1;
            return res;
        }
    }
    return res;
}

时间复杂度：$O(n)$，两个指针的移动总次数最多为n
空间复杂度：$O(1)$

method 2: 二分法

固定一个数，然后二分找另一个数

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res(2);
    for (int i = 0; i < nums.size(); i++) {
        int l = i, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[i] + nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        if (nums[i] + nums[l] == target) {
            res[0] = i + 1;
            res[1] = l + 1;
            return res;
        }
    }
    return res;
}