leetcode:1.两数之和

水深无声 2022-03-12 16:37 232阅读 0赞

### 题目描述： ###

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个 整数，并返回他们的数组下标。  
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

##### 示例： #####

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

##### 题目难度：简单 #####

##### 分析： #####

很简单的一道题目，没什么好说的。注意算法复杂度和时间复杂度即可。

##### 解法一：暴力解法 #####

直接双层for循环，看看存不存在两个值相加等于target即可，注意的点就是外层和内层的取值范围，避免做无用功。还有就是如果找到了，立马return回去就行了， 这样的话就不需要继续循环了，比较节省时间。代码如下：

###### java: ######

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            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;
        }
    }

###### python: ######

class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            for i in range(len(nums) - 1):
                for j in range(i + 1, len(nums)):
                    if nums[i] + nums[j] == target:
                        return [i, j]

##### 小结： #####

时间复杂度 O ( n 2 ) O(n^\{2\}) O(n2)

##### 解法二：两遍hash表 #####

先把数组中的每个元素放在HashMap中，这样查找的时候可以用 O ( 1 ) O(1) O(1)的时间复杂度查询出来。注意的点是：因为数组元素不可以重复使用，所以以值为key，下标为value，然后加一个限定条件即可。

###### java: ######

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

###### python: ######

class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            dict_map = { }
            for i, v in enumerate(nums):
                dict_map[v] = i
    
            for i, v in enumerate(nums):
                temp = target - v
                if (temp in dict_map) and (i != dict_map[temp]):
                    return [i, dict_map[temp]]

##### 小结： #####

时间复杂度 O ( n ) O(n) O(n)，这里虽然是遍历了两次，但是hash表的时间复杂度是 O ( 1 ) O(1) O(1)，所以时间复杂度为 O ( n ) O(n) O(n)。

##### 总结： #####

leetcode第一题，所以比较简单，初学算法的话，也可以很快的想到暴力解法。