1. Two Sum 两数之和

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/open in new window
• 个人公众号：负雪明烛
• 本文关键词：two sum, 两数之和，题解，leetcode, 力扣，Python, C++, Java

@TOC

# 题目描述

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, and you may not use the same element twice.

Example:

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

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

# 解题方法

# 字典+两次遍历

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
for i, num in enumerate(nums):
dic[num] = i
for i, num in enumerate(nums):
if target - num in dic and dic[target - num] != i:
return [i, dic[target - num]]

# 字典+一次遍历

public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
if(map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]), i};
}else{
map.put(nums[i], i);
}
}
return new int[2];
}
}

python解法如下，打败100%的提交。

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
N = len(nums)
pos = dict()
for i, num in enumerate(nums):
if target - num in pos:
return [pos[target - num], i]
else:
pos[num] = i
return [0, 0]

# 双指针

C++代码如下：

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> copy = nums;
sort(nums.begin(), nums.end());
int left = 0;
int right = nums.size() - 1;
while (left != right) {
if (nums[left] + nums[right] == target)
break;
else if (nums[left] + nums[right] > target)
right --;
else
left ++;
}
vector<int> res(2, -1);
for (int i = 0; i < copy.size(); ++i) {
if (copy[i] == nums[left] && res[0] == -1) {
res[0] = i;
} else if (copy[i] == nums[right]) {
res[1] = i;
}
}
return res;
}
};

# 日期

2017 年 5 月 18 日 2018 年 11 月 22 日