两数之和能否通过特定算法快速计算？

本文共计565个文字，预计阅读时间需要3分钟。

1. 两数之和 + 暴力解法：通过两个for循环逐个遍历，判断是否存在符合条件的结果。1. 初始已有数据判断，例如数字比较目标值大就不需再判断，直接跳过，其实是不行的，因为可能存在负数。

1. 两数之和

• 暴力解法：通过两个for循环逐步遍历，判断是否有符合条件的答案
• 1.初始有对数据进行判断，比如数字比目标值大就不用判断，直接跳过，其实是不行的，因为里面有负数，最后相减也可以得出正确答案，这是最初版本。

class Solution { public int[] twoSum(int[] nums, int target) { int[] dp = new int[2]; for(int i = 0 ;i <nums.length;i++){ if(nums[i]>Math.abs(target)){ continue; }else{ for(int j = i+1;j<nums.length;j++){ if(target == nums[i]+nums[j]){ dp[0] = i; dp[1] = j; } } } } return dp; } }

• 2.之后发现有负数这种情况后，直接取消了判断，但这样会增加时间复杂度，没有做好优化。

class Solution { public int[] twoSum(int[] nums, int target) { int[] dp = new int[2]; for(int i = 0 ;i <nums.length;i++){ for(int j = i+1;j<nums.length;j++){ if(target == nums[i]+nums[j]){ dp[0] = i; dp[1] = j; } } } return dp; } }

• 哈希表法:先将数据存入哈希表中，再使用目标值依次减去数组中的数据，再从哈希表中找是否有符合条件的值，如果有，将下标传给result数组，返回结果。

class Solution { // HashMap // N is the size of nums // Time Complexity: O(N) // Space COmplexity: O(N) public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; //定义hashMap HashMap<Integer,Integer> map = new HashMap<>(); for(int i=0;i < nums.length;i++){ //将所有数据存入hash表中 map.put(nums[i],i); } //使用目标值减去数组中的值，查看表中是否有符合条件的值就返回 for(int j=0;j < nums.length; j++){ int diff = target - nums[j]; if(map.containsKey(diff)&&map.get(diff)!=j){ result[0] = j; result[1] = map.get(diff); return result; } } return result; } }