题目
思路和算法
暴力枚举数组中每一个数x,寻找数组中是否存在target-x
c++:
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i= 0; i<nums.size(); i++){ for(int j=i+1; j<nums.size(); j++){ if(nums[i]+nums[j] == target){ return {i,j}; } } } return {}; } };
java:
class Solution { public 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[i]+nums[j] == target){ return new int[]{i,j}; } } } //返回一个长度为0的数组 return new int[0]; } }
复杂度分析
思路和算法
注意方法一中查找target-x的复杂度过高,因此我们可以用哈希表存储值和下标的对应关系
,将复杂度降为O(1)
c++:
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for (int i = 0; i < nums.size(); i++) { m[target - nums[i]] = i + 1; } for (int i = 0; i < nums.size(); i++) { if (m[nums[i]]&& (i != m[nums[i]] - 1)) { return {i, m[nums[i]] - 1}; } } return {}; } };
java
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>(); for(int i=0; i<nums.length;i++){ if(hashMap.containsKey(target-nums[i])){ return new int[]{i,hashMap.get(target-nums[i])}; } hashMap.put(nums[i], i); } return new int[0]; } }
复杂度分析