LeetCode——Problem1:two sum

早就想刷LeetCode了，但一直在拖，新学期开学，开始刷算法。

我准备从Python和C++两种语言刷。一方面我想做机器学习，以后用Python会比较多，联系一下。另一方面C++或者C语言更接近底层，能够让我更深入的理解算法。

1、题目

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]

2、Python解法

我是这样写的

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

nums=[2,7,11,15]
target=9
result=Solution()
result_num=result.twoSum(nums,target)
print(result_num)

其中遇到了一个错误

TypeError: twoSum() missing 1 required positional argument: 'target'

这个因为之前我后面几行的代码是

1 nums=[2,7,11,15] 
2 target=9
3 result_num=Solution.twoSum(nums,target) 
4 print(result_num)

没有初始化Solution类，改成上面第23行先初始化一下就行了

然而。。。这个代码完全不能通过LeetCode的测试。算法复杂度太高

然后我看了别人写的

 1 class Solution(object):
 2     def twoSum(self,nums,target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         n = len(nums)
 9         result = {}
10         if n <= 1:
11             return False
12         else:
13             for i in range(n):
14                 if nums[i] in result:
15                     return result[nums[i]],i
16                 else :
17                     result[target-nums[i]]=i
18 
19 
20 nums=[2,7,11,15]
21 target=9
22 result=Solution()
23 result_num=result.twoSum(nums,target)
24 print(result_num)

就是借用字典的key-value进行的匹配，算法复杂度仅为O(n)

然后还看到了这个

1 class Solution(object):
2 def twoSum(self, nums, target):
3 
4     for ind, num in enumerate(nums):
5         if target-num in nums and nums.index(target-num) != ind:
6             return [ind, nums.index(target-num)]
7     return -1

直接利用了列表的索引。

运行速度仅为4ms

但是其中肯定用到了其他遍历比如nums.index(target-num)。这就是Python最大的优势吧。简单，容易理解。

3、C语言解法

说实话，我还没系统的学过C++呢。专业不是这类的，学校不给我们安排课。这次先用C。等我慢慢学学C++再用C++

我的解法：

 1 #include<stdio.h>
 2 
 3 
 4 /**
 5  * Note: The returned array must be malloced, assume caller calls free().
 6  */
 7 int* twoSum(int* nums, int numsSize, int target) {
 8     int i,j;
 9     static int result[2];
10     for(i=0;i<numsSize-1;i++)
11     {
12        for(j=i+1;j<numsSize;j++)
13        {
14         if(*(nums+i)+*(nums+j)==target)
15         {
16             *result = i;
17             *(result+1)=j;
18         }
19        }
20     }
21     return(result);
22 }
23 int main()
24 {
25     int nums[4]={2,7,11,15};
26     int target = 9;
27     int numSize=4;
28     int *result;
29     result=twoSum(nums,numSize,target);
30     printf("succeed
");
31     for(int i=0;i<2;i++)
32     {
33     printf("%d
",*(result+i));
34     }
35 
36 return 0;
37 }

只是简单的遍历。丝毫没有新意

大神解法：

 1 /**
 2  * Note: The returned array must be malloced, assume caller calls free().
 3  */
 4 
 5 int* twoSum(int* nums, int numsSize, int target) {
 6     int i, max, min;
 7     max = min = nums[0];
 8     for(i = 0; i < numsSize; i++) {
 9         if(nums[i] > max) max = nums[i];
10         if(nums[i] < min) min = nums[i];
11     }
12     
13     int *map   = (int*)calloc((max-min+1), sizeof(int));
14     int *reval = (int*)malloc(sizeof(int)*2);
15     
16     for(i = 0; i < numsSize; map[nums[i]-min] = ++i) {
17         int lookfornum = target - nums[i];
18         if(lookfornum < min || lookfornum > max) continue;
19         int dis = lookfornum - min;
20         if (map[dis]) {         
21             reval[0] = i;
22             reval[1] = map[dis] -1;
23             break;
24         }
25     }
26     
27     return reval;
28     
29 }

这个是所有解法里运行的最快的了。引用了我根本没听说过的map。我也很无奈呀。还要注意内存的申请呀。不过我好像没看到free

今天比较晚了。我还想再画画程序流程图的，既然做了，就要做透。