leetcode1.两数之和

题目描述 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解 暴力法 复杂度分析 时间复杂度：O(n ^2 ) 空间复杂度：O(1) c++ class Solution { public: vector twoSum(vector& nu 【题目名称】：LeetCode1.两数之和 【问题描述】： 这道题目是LeetCode中的经典问题，目标是找到一个整数数组`nums`中两个数的索引，使得它们相加等于给定的目标值`target`。数组中每个输入只会对应一个答案，而且不能使用相同的元素两次。 【暴力法解法】： 暴力法的基本思路是使用两层循环，外层循环遍历数组的每个元素，内层循环则从当前元素的下一个元素开始查找，直到数组末尾。如果内层循环中找到了与当前元素相加等于目标值的数，则返回这两个元素的索引。这种方法的时间复杂度是O(n^2)，空间复杂度是O(1)，因为只用到了常数个变量。以下是不同编程语言的实现： - C++: ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int len = nums.size(); for(int i=0; i<len; i++){ for(int j=i+1; j<len; j++){ if(nums[i]==target-nums[j]){ return {i, j}; } } } return {}; } }; ``` - Java: ```java class Solution { public int[] twoSum(int[] nums, int target) { int len = nums.length; for(int i=0; i<len; i++){ for(int j=i+1; j<len; j++){ if(nums[i]+nums[j]==target){ return new int[] { i, j }; } } } return new int[] {}; } } ``` - Python3: ```python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: lens = len(nums) for i in range(lens): for j in range(i+1, lens): if(target==nums[i]+nums[j]): return [i, j] return [] ``` - JavaScript: ```javascript var twoSum = function(nums, target) { let len = nums.length; for(let i=0; i<len; i++){ for(let j=i+1; j<len; j++){ if(target==nums[i]+nums[j]){ return [i, j]; } } } return []; }; ``` - Go: ```go func twoSum(nums []int, target int) []int { for i, vi := range nums { for _, vj := range nums[i+1:] { if target == vi+vj { return []int{i, i + 1 + j} } } } return []int{} } ``` 【哈希表解法】： 为了提高效率，我们可以使用哈希表（如C++中的`unordered_map`、Java中的`HashMap`、Python3中的字典或JavaScript中的对象等）来存储数组元素及其索引。在遍历数组的过程中，对于每个元素，我们检查哈希表中是否存在目标值减去当前元素的值。如果存在，就返回这两个值的索引；如果不存在，就将当前元素及其索引存入哈希表。这种方法的时间复杂度降低到O(n)，空间复杂度也是O(n)，因为需要存储数组中的一半元素。以下是哈希表解法的代码示例： - C++: ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for(int i=0; i<nums.size(); i++){ if(m.find(target-nums[i])!=m.end()){ return {m[target-nums[i]], i}; } m[nums[i]] = i; } return {}; } }; ``` - Java: ```java class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } return new int[] {}; } } ``` - Python3: ```python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashMap = {} lens = len(nums) for i in range(lens): if target - nums[i] in hashMap: return [hashMap[target - nums[i]], i] hashMap[nums[i]] = i return [] ``` 通过哈希表解法，我们可以在较短的时间内解决这个问题，尤其在数据规模较大时，性能优势更为明显。