LeetCode：两数之和

桃扇骨 2022-12-18 09:00 4阅读 0赞

![在这里插入图片描述][20201026133356480.png_pic_center]

题目：

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/two-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

> 思路：  
> 我们可以用两层for循环来遍历这个nums，然后如果target-对应某个数据等于一个数，那么这两个数的下标就是所要求的：  
> 第一种方式：

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

时间复杂度为：O(n\*n)

> 可看这样的时间复杂度还是太大了，如果遇到最坏的情况下，就直接变成 了n\*n的形式，效率太低了：  
> 下面我们采用哈希表降低时间复杂度：

思路：

> 我们可以首先把nums数组 中的数据放入到哈希表中，然后再遍历一次nums取出里面对应的值进行判断，看是否为对应的target，这里注意，目标元素不能为nums\[i\]本身。

第二种方式：

public static int[] twoSum2(int[] nums, int target) { 
            HashMap<Integer, Integer> map = new HashMap<>();
            //将数组中的数据放入到哈希表中
            for (int i = 0; i < nums.length; i++) { 
                map.put(nums[i], i);
            }
    
            //然后遍历，看是否满足条件，哈希表中的key就是值
            for (int i = 0; i < nums.length; i++) { 
                int temp = target - nums[i];
                if (map.containsKey(temp) && map.get(temp) != i){ 
                    return new int[]{ i,map.get(temp)};
                }
            }
            return null;
        }

时间复杂度为：O(n)  
这样就把时间复杂度将到n！

[20201026133356480.png_pic_center]: /images/20221122/2f67d98122b94d7b8ee781a0f7047c08.png