LeetCode系列（一）--------两数之和（简单）

柔光的暖阳◎ 2023-07-17 15:39 36阅读 0赞

# 描述 #

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

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

示例:

给定 nums = \[2, 7, 11, 15\], target = 9

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9

所以返回 \[0, 1\]

# 难度：简单 #

# 一、暴力法 #

## 思路 ##

直接进行循环，因为有唯一答案，那么有结果时直接return即可

## 代码 ##

class Solution {
        public int[] twoSum(int[] nums, int target) {
            for(int x = 0;x < nums.length-1;x++){
                for(int y = x+1;y<nums.length;y++){
                    if(nums[x] + nums[y] == target) return new int[]{x,y};
                }
            }
            return new int[]{};
        }
    }

## 复杂度分析 ##

时间复杂度：O(n^2)

对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为O(n^2)

空间复杂度：O(1)

# 二、两遍Hash表算法 #

## 思路 ##

这个方法时典型的空间换取时间算法

我们在暴力法中，连续进行了两次遍历查找，导致时间复杂度成为O(n^2)，引入Hash表可以将遍历的时间复杂度变为O(1)

这种方法巧用了HashMap中对Key的操作，我们将数组内的值放到key上，下标放到value上，通过计算key值来得到是否map中有我们需要的另一个值，如果有，那么获取到那个key所对应的value，也就是得到了我们在数组中的下标

有一点需要注意的是，在条件判断是否存在该值的时候，应添加去重判断，举例：target = 6，数组中某值等于3（有且仅有一个），此时去查找key，肯定会返回一个有一个值与当前值之和等于6，但是这不是我们要找的值，此时会返回\{x,x\}

## 代码 ##

class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> intMap = new HashMap();
            for (int i = 0; i < nums.length; i++) {
                intMap.put(nums[i], i);
            }
            for (int i = 0; i < intMap.size(); i++) {
                int complement = target - intMap.get(i);
                if (intMap.containsKey(complement) && intMap.get(complement) != i) return new int[]{i, intMap.get(complement)};
            }
            return new int[]{};
        }
    }

## 复杂度分析： ##

时间复杂度：O(n)，我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到O(1) ，所以时间复杂度为 O(n)

空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。

# 三、一遍Hash算法 #

## 思路 ##

我们遍历数组时，每往hash中添加一个元素，我们就可以拿当前元素获取差值，并与hash中已经存在的元素进行对比，如果有满足条件的key，就可以直接返回，这样就只需要一次遍历就可以完成所有操作

## 代码 ##

class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> intMap = new HashMap();
            for (int i = 0; i < nums.length; i++) {
                intMap.put(nums[i], i);
                int com = target - nums[i];
                if (intMap.containsKey(com) && intMap.get(com) != i) return new int[]{intMap.get(com),i};
            }
            return new int[]{};
        }
    }

复杂度分析：

时间复杂度：O(n)，我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。

空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

# 四、总结 #

1.空间换区时间

2.巧用hash表

3.积累知识，打开思路