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

Example:

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

给一个无序数组和一个target，返回两个indice使得两个相加的值为target。

解答：

思路一：

最简单的思路，暴力，从头到尾搜索，但是时间复杂度过高，空间复杂度也很高。

class Solution(object):

    def twoSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

        n = len(nums)

        for i in range(0,n-1):

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

                temp = nums[i] + nums[j]

                if temp==target:

                    return [i, j]

        return []

思路二：

想着排序后类似二分，时间复杂度变为o(n)，结果忽略了返回原数组的indice，排序后破坏了数组的结构。

class Solution(object):

    def twoSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

        nums.sort()

        n = len(nums)

        i = 0

        j = n-1

        while(1):

            temp = nums[i] + nums[j]

            if temp<target:

                i = i + 1

            elif temp>target:

                j = j - 1

            elif temp==target:

                return [i,j]

            elif i>=j:

                break

        return []

反思：

太久coding，python的函数都不熟练了，比如想写个循环，都在想怎么写索引，比如list的长度，len(list)，list排序list.sort(parameter)；写多了就熟练了，将平时用到的记录下来。

边界考虑比较混乱，代码里面一堆if else终止，return也好几个，代码不规范，空格不知道哪些地方该加；加强代码规范性，系统整理一个文档，并通过coding强化。

思路不清晰，多刷题。