题目描述

题目链接:https://leetcode.com/problems/two-sum/

Given an array of integers nums and an integer target,return indices of the two 
numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not
use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
 

Constraints:

2 <= nums.length <= 105
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

博主初始思路

可以看出我面对这道题最开始思考还是简单的，嵌套循环，暴力相加，如果相同那么就返回正确的索引，目前时间复杂度是O(n2)，空间复杂度是O(n)，但是这个解法是没有灵魂的，看一下下面的优秀解法

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

时间复杂度为O(n)，但是空间复杂度为O(2n)的解题思路

这个思路比较巧妙，在你遍历数组中的每个元素的时候，target-nums[i]你就会知道了，提前知道自己的另一半，然后把这个另一半然后放入到一个map中，这样遇到自己的另一半时，就会提前知道了
https://stackoverflow.com/questions/1055243/is-a-java-hashmap-search-really-o1
http://stackoverflow.com/questions/15469795/why-hashmap-lookup-is-o1-i-e-constant-time

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> tmp = new HashMap<>();
        int[] result = new int[2];
        for(int i=0; i<nums.length; i++){
            if( tmp.get( nums[i]) != null){
                result[0] = i;
                result[1] = tmp.get(nums[i]);
                return result;
            }else{
                tmp.put( target-nums[i], i);
                continue;
            }
            
        }
        return null;
    }
}