---恢复内容开始---

1.给一个int数组，和一个目标值，返回两个数数组中和等于目标值的两个数的index数组。

我的（38ms）：

Time complexity : O(n^2)

Space complexity : O(1)

public int[] twoSum(int[] nums, int target) {        for (int i = 0; i < nums.length-1; i++) {            for (int j = i + 1; j < nums.length; j++) {                if (nums[i] + nums[j] == target) {                    return new int[]{i, j};                }            }        }        return null;    }

评价：发现和网上的第三种一样，不怎么样，但还是摆在前面，啦啦啦啦

大神的(7ms)：

Time complexity : O(n) - Array containing n elements is traversed only once. Each look up in the hash-table takes a constant time.

Space complexity : O(n) - The extra space required depends on the number of items stored in the hash table, which can be at most n elements.

public int[] twoSum(int[] A, int target)     {        HashMap
     
       map = new HashMap
      
       ();                for(int i = 0; i < A.length; i++)        {            int complement = target - A[i];                        if(map.containsKey(complement))                return new int[]{map.get(complement), i};        // Return index of complement and the index of current element            else                map.put(A[i], i);                                // Store current element and its index in the hash-table                        }        return new int[2];    }
      
     

算法思路：减少一次循环，使用HashMap保存数组元素（key）,下标（value）。

直接使用目标值和第一层循环的元素算出和当前元素匹配的值。

然后免去第二层循环直接使用containsKey方法判断这个用来匹配的值是否存在map中，是就太好了，不是放进map备用。

大神的：

Time complexity : O(n.log n) - Time required for sorting an Array

Space complexity : O(n) - space for an additional array

public int[] twoSum(int[] A, int target)    {        int[] B = Arrays.copyOf(A, A.length);        Arrays.sort(B);                int start = 0;        int end = A.length - 1;                while(start < end)        {            if(B[start] + B[end] == target)            {                int i = 0;                int j = A.length - 1;                while(i < A.length && A[i] != B[start])                    i++;                while(j >= 0 && A[j] != B[end])                    j--;                return new int[]{i, j};            }            else if(B[start] + B[end] < target)            {                start++;            }            else            {                end--;            }            }        return new int[2];        }

分析：复制数组并顺序排序，想象这些数字都在X轴上。从两头开始相加两头的值，如果刚好，返回。如果小于目标值，那么左边右移一位。如果大于目标值，右边的左移，继续。

 

2.现给出两个非空链表，它们表示两个非负整数。数字以相反的顺序存储，每个节点都包含一个数字。将这两个数字相加并以链表的形式返回。

 

---恢复内容结束---