LeetCode 1 Two Sum 題解

Problem：

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

Solution：

O(n2) runtime, O(1) space – Brute force:

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target – x. As finding another value requires looping through the rest of array, its runtime complexity is O(n2).

O(n) runtime, O(n) space – Hash table:

We could reduce the runtime complexity of looking up a value to O(1) using a hash map that maps a value to its index.

Average Rating: 4.5 (874 votes)

Is this solution helpful? Read our book to learn more.

題目大意：

給定一個數組和一個目標整數，求在數組中的兩個和為目標函數的下標，第一個下標要小於第二個下標（確保有且只有一個結果）

解題思路：

兩種方法，一種是暴力破解，找到一個數之後在數組中找target減去這個數的數，時間復雜度O(n^2)，效率太低，TLE

第二種方法采用可以經常想到的Hash來解決（本文就是用這種方法），Hash存儲與查找

另想到的方法有二叉搜索樹和二叉平衡樹，B樹，不過沒有代碼實現，不知道對不對。

下面是C語言，C++，Java和Python的解題代碼，歡迎批評指正。

Java源代碼：

import java.util.*;
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap();
        for(int i=0;i
C語言源代碼（C代碼由於自己實現了Map，所以代碼比較長）：


#include
#include
#define HASH_SIZE 10000
struct node{
	int value;
	int key;
	struct node* next;
};
struct node* data[HASH_SIZE];

int contains(int key){
	int hash = abs(key)%HASH_SIZE;
	struct node* p = data[hash];
	while(p!=NULL){
		if(p->key==key)return 1;
		p=p->next;
	}
	return 0;
}
void put(int key,int value){
	int hash = abs(key)%HASH_SIZE;
	struct node* p = data[hash];
	struct node* s = (struct node*)malloc(sizeof(struct node));
	s->key=key;
	s->value=value;
	s->next=NULL;
	if(p==NULL){
		data[hash] = s;
		return;
	}
	while(p->next!=NULL){
		p=p->next;
	}
	p->next=s;
}
int get(int key){
	int hash = abs(key)%HASH_SIZE;
	struct node* p = data[hash];
	while(p!=NULL){
		if(p->key==key)return p->value;
		p=p->next;
	}
	return 0;
}
int abs(int value){
	return value>0?value:-value;
}
int* twoSum(int* nums, int numsSize, int target) {
	 int* res = (int*)malloc(sizeof(int)*2);
	 int value;
	 for(value=0;value
C++源代碼（采用STL的map）：
#include
#include
#include
Python源代碼（不得不說Python代碼量就是少啊，爽）：


class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer[]}
    def twoSum(self, nums, target):
        map={};
        for i in range(0,len(nums)):
            if map.has_key(target-nums[i]):
                return map[target-nums[i]],i+1
            map[nums[i]]=i+1
        return 0,0