数据结构篇-04：哈希表解决TwoSum问题

本文对应 力扣高频100 中的“1、两数之和”

---

对于“两数之和”问题，我们常用的方法是暴力遍历 或者 双指针方法。但是后者只有在数组有序的情况下才能使用。

当数组无序时，使用哈希表是最好的选择。通过使用哈希表来记录元素，可以让我们在时间复杂度O（1）中获得目标元素

接下来我会逐一演示以上三种方法的代码示例

哈希表

寻找能与当前元素 nums[i] 相加为目标值 target 的元素

int[] twoSum(int[] nums,int target) {int n = nums.length;index<Integer,Integer> index = new HashMap<>();//将数组元素构建哈希表for(int i = 0;i < n;i++){index.put(nums[i],i);}//寻找目标元素for(int i = 0;i < n;i++){int other = target - nums[i];//当哈希表中有这个元素且这个元素不是nums[i]本身时if(index.containsKey(other) && index.get(other) != i){return new int[]{i,index.get(other)};}}return new int[]{-1,-1};
}

暴力遍历

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 new int[]{-1,-1};
}

双指针

对于双指针的使用，后面谈到nSum问题时我会详细讲述

int[] twoSum(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {return new int[]{left, right};} else if (sum < target) {left++; // 让 sum 大一点} else if (sum > target) {right--; // 让 sum 小一点}}// 不存在这样两个数return new int[]{-1, -1};
}