每日算法——letcode系列

問題 Two Sum

Difficulty:<strong>Medium</strong></br>

Given an array of integers, 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. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

// C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
    }
};

翻譯

兩數(shù)和

難度系數(shù)：中等

給定一個整數(shù)數(shù)組，找到兩數(shù)和等于指定的數(shù)的這兩個數(shù)

函數(shù)twoSum應(yīng)返回這兩個數(shù)的索引，且第一個索引要比第二個索引要小。注意兩個索引不是0為基的索引

你可以假定每個輸入都有一個答案就好。（也就是有可能有很多數(shù)都加起來都等于指定的數(shù)，找到其中一種就好）

思路

方案一：暴力窮舉

這里有一點技巧，兩個循環(huán)，外層循環(huán)的最后應(yīng)為size-1, 內(nèi)層循環(huán)的開始搜索值就比外層循環(huán)的初始值大1， 因為數(shù)組中如果第一個數(shù)沒有和他加起來等于指定的數(shù)，那他不應(yīng)再被搜索。

方案二： hashmap法

方案一中， 其實內(nèi)層循環(huán)都在搜索加起來是否等于指定數(shù)，其時間復(fù)雜度為O(n) ,用hash的辦法，數(shù)組元素為key, 索引為value, 這樣可以把內(nèi)層循環(huán)的時間復(fù)雜度降為O(1)

代碼

方案一：

// C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = static_cast<int>(nums.size());
        vector<int> result;
        for (int i = 0; i < size - 1; ++i) {
            for (int j = i + 1; j < size; ++j){
                if (nums[i] + nums[j] == target){
                    result.push_back(i + 1);
                    result.push_back(j + 1);
                    return result;
                }
            }
        }
        return resul;
    }
};

方案二：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       int size = static_cast<int>(nums.size());
        vector<int> result;
        unordered_map<int, int> temp;
        for (int i = 0; i < size; ++i) {
            if (temp.find(target - nums[i])  == temp.end()){
                temp[nums[i]] = i;
            }
            else{
                result.push_back(temp.at(target - nums[i]) + 1);
                result.push_back(i + 1);
                break;
            }
        }
        return result;
    }
};

前文延伸解決

分析

如果只有一個重復(fù)數(shù)，可以把所有數(shù)相加（注意和越界超出int_max)，減去高斯和(1到256f求和)，得到的差就為要找的數(shù)，但如果數(shù)太多，還是得把數(shù)讀完才能找到，hashmap的辦法有可能沒讀完就能找到，但這個方法很取巧，為解決越界，還可以用位操作。