【LeetCode】 1. 两数之和（JAVA）时间复杂度O(n2)和O(n)两种解决方案

缺乏、安全感 2021-06-22 15:36 273阅读 0赞

## 题目 ##

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例:**

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

[https://leetcode-cn.com/problems/two-sum/][https_leetcode-cn.com_problems_two-sum]

## 暴力方式 ##

### 解题思路 ###

思路很简单，遍历整个数组，先找第一个值nums\[i\]，然后遍历找另外一个值nums\[j\]，两个值相加，看看结果是不是target

### 代码 ###

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            if (nums.length < 2) return null;
            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;
        }
    }

> 时间复杂度O（n2）：双层遍历，所以时间复杂度是n2  
> 空间复杂度O（1）：没有使用额外的空间

## 使用HashMap方式 ##

### 解题思路 ###

要找的是两个数字的和，一定少不了的是数组从头到尾的遍历，我们可以把遍历过的值都记录下来，这样我们就可以在遍历过的值中进行检索了。

所以我们使用java提供的数据机构HashMap，把遍历过的值都放到HashMap中，Key为值，Value为索引。

那么，在遍历的时候，每遍历一个值nums\[i\]的时候，先判断HashMap中是否含有target-nums\[i\]，如果有，则直接返回，没有的话就继续向下遍历，这样我们只需要遍历一次即可。

### 代码 ###

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

> 时间复杂度O（n）：数组从头到尾遍历了一遍，所以时间复杂度为n  
> 空间复杂度O（n）：定义了一个HashMap用来存储遍历过的值，所以空间复杂度为n

[https_leetcode-cn.com_problems_two-sum]: https://leetcode-cn.com/problems/two-sum/