leetcode1.两数之和

题目链接

解法一: 暴力求解

暴力求解的思路很简单，依次遍历数组的每个数，看这个数字和除了这个数字之外的其他数字的和是否等于target，这样就需要两层遍历，时间复杂度为O(n ^ 2)。
代码如下：

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){
                    return new int[]{i , j};
                }
            }
        }
        return null;
    }
}

OJ测试用时自然很差

解法二: 使用哈希表

代码如下：
在leetcode-cn题解区,有对于这种解法很好的说明：
题解

import java.util.HashMap;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]) , i};
            }else{
                map.put(nums[i] , i);
            }
        }
        return null;
    }
}

因为对于哈希表的增删改查操作都可以认为是O(1)的，而我们只需要遍历一次数组，所以该算法的时间复杂度为O(n)，不过另外地使用了哈希表这种数据结构，额外空间复杂度为O(n)。
OJ的测试结果如下：