【LeetCode】1. Two Sum – TK-Xiong`s Blog

好久没刷算法了，闲来无事，刚学了点Python，找个简单题做做，不料惨被虐…

题目很简单，主要还是不熟悉Python语法，哈哈哈哈。

题目链接:

https://leetcode.com/problems/two-sum/description/

https://leetcode-cn.com/problems/two-sum/submissions/

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

Subscribe to see which companies asked this question

代码如下：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        num = len(nums)
        for i in range(num):
            for j in  range(i + 1, num):
                if(nums[i] + nums[j] == target):
                    return [i, j]
        return []

class Solution(object):

def twoSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[int]

"""

num = len(nums)

for i in range(num):

for j in range(i + 1, num):

if(nums[i] + nums[j] == target):

return [i, j]

return []

哈哈哈哈…我可不会说我写这么简单的代码语法报错十几次，哈哈哈哈哈。

C++ 代码如下:

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

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

for(int i = 0; i < nums.size()-1; i++)

{

for(int j = i + 1; j < nums.size(); j++)

{

if(nums[i] + nums[j] == target)

{

vector<int> v;

v.push_back(i);

v.push_back(j);

return v;

}

};

最新版6ms代码: 忘记看效率了，结果一看，二维循环慢的一批，用 hashMap实现了一下。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> v;
        for(int i = 0; i < nums.size(); i++)
        {
            int findNum = target-nums[i];
            if(m.find(findNum) != m.end())
            {
                v.push_back(m[findNum]);
                v.push_back(i);
                return v;
            }
            m[nums[i]] = i;
        }
        return v;
    }
};

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> m;

vector<int> v;

for(int i = 0; i < nums.size(); i++)

{

int findNum = target-nums[i];

if(m.find(findNum) != m.end())

{

v.push_back(m[findNum]);

v.push_back(i);

return v;

}

m[nums[i]] = i;

}

return v;

}

};

需要无序容器，快速查找删除，不担心略高的内存时用unordered_map；有序容器稳定查找删除效率，内存很在意时候用map。

没什么区别，很简单的二维循环就可以解决，后面3 sum就有意思了。

Go 语言版本：

func twoSum(nums []int, target int) []int {
    kvMap := map[int]int {}
    
    for i, v := range nums {
        value, ok := kvMap[target - v]
        if ok {
            return []int {value, i}
        }
        kvMap[v] = i
    }

    return nil
}

func twoSum(nums []int, target int) []int {

kvMap := map[int]int {}

for i, v := range nums {

value, ok := kvMap[target - v]

if ok {

return []int {value, i}

}

kvMap[v] = i

}

return nil

}

思路一致，就是语法不一样。 Go只用了4ms，内存3.8M，在LeetCode上比CPP小很多。

【LeetCode】1. Two Sum

Tagged on: C++ LeetCode Python