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

Example:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路：

1
2
3
4
1.题目未说明是有序数组，因此，为了方便我们进行处理，首先需要进行排序。
2.第二步进行查找，找出排序之后小于target的元素。
3.在剩下的数组中进行遍历，找出两个数。
4.找出这两个数对应原数组的下标。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def twoSum(nums, target):
  item_index = nums
  arr = [i for i in nums if i < target]
  arr.sort()

  for i in range(len(arr)):
    for j in range(i+1,len(arr)):
      if arr[i] + arr[j] == target:
        return([findIndex(arr[i],item_index),
               findIndex(arr[j],item_index)])

def findIndex(item,item_index):
  for index in range(len(item_index)):
    if item == item_index[index]:
      return index

其他解法：

1
2
3
4
5
6
def twoSum(nums, target):
  process={}
  for index in range(len(nums)):
    if target-nums[index] in process:
      return [process[target-nums[index]],index]
        process[nums[index]]=index

注：这个解法是在网上看到的，确实简单许多，采用hashtable，数值记为key,value记为index，target-num[index]作为搜索条件。