LeetCode_双指针_哈希表_简单_1.两数之和

浅浅的花香味﹌ 2023-10-06 17:57 10阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）
 *  4.扩展

## 1.题目 ##

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。  
**你可以假设每种输入只会对应一个答案**。但是，数组中同一个元素在答案里不能重复出现。**你可以按任意顺序返回答案。**

**示例 1：**  
输入：nums = \[2,7,11,15\], target = 9  
输出：\[0,1\]  
解释：因为 nums\[0\] + nums\[1\] == 9，返回 \[0,1\] 。

**示例 2：**  
输入：nums = \[3,2,4\]，target = 6  
输出：\[1,2\]

**示例 3：**  
输入：nums = \[3,3\]，target = 6  
输出：\[0,1\]

**提示：**  
2 <= nums.length <= 104  
\-109 <= nums\[i\] <= 109  
\-109 <= target <= 109  
只会存在一个有效答案

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/two-sum

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法应该是最容易想到的方法，其思想是使用两层 for 循环，遍历数组中的每一个数 x，查找数组中是否存在 target - x，若存在，将结果保存到数组 res 中，并退出循环即可。

（2）哈希表  
先创建一个哈希表，对于数组中的每一个 x，首先查询哈希表中是否存在 target - x，如果不存在，则将 x 插入到哈希表中并继续访问下一个 x，否则将答案保存到数组 res 中。该算法提高了查找效率，不过由于需要用到一个哈希表，这样一来增加了空间复杂度。

相关题目：  
[LeetCode\_双指针\_中等\_15.三数之和][LeetCode_15.]  
[LeetCode\_双指针\_中等\_16.最接近的三数之和][LeetCode_16.]  
[LeetCode\_双指针\_中等\_18.四数之和][LeetCode_18.]  
[LeetCode\_双指针\_中等\_167.两数之和 II - 输入有序数组][LeetCode_167._ II -]  
[LeetCode\_哈希表\_中等\_454.四数相加 II][LeetCode_454._ II]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    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};
                    }
                }
            }
            return new int[0];
        }
    }

//思路2————哈希表
    class Solution {
        
    	public int[] twoSum(int[] nums, int target) {
        
    	    Map<Integer, Integer> hashMap = new HashMap<>();
    	    for (int i = 0; i < nums.length; i++) {
        
    	        //containsKey(): 检查 hashMap 中是否存在指定的 key 对应的映射关系
    	        if (hashMap.containsKey(target - nums[i])) {
        
    	            //get(): 获取指定 key 对应的 value
    	            return new int[]{
        hashMap.get(target - nums[i]), i};
    	        }
    	        //当前未找到 target - nums[i]，将 nums[i] 以及其数组下标保存到哈希表 hashMap 中
    	        hashMap.put(nums[i], i);
    	    }
    	    return new int[0];
    	}
    }

## 4.扩展 ##

（1）如果数组 nums 本身是有序的，则可以使用双指针来找到和为目标值 target 的那两个整数，并返回它们在数组中的下标，见[LeetCode\_双指针\_中等\_167.两数之和 II - 输入有序数组][LeetCode_167._ II -]这题。代码实现如下：

class Solution {
        
    	public int[] twoSum(int[] nums, int target) {
        
    	    //前提：数组 nums 是有序的
    	    
    	    //定义双指针
    	    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) {
        
    	            //增大sum的值，即将 left 向右移动
    	            left++;
    	        } else {
        
    	            //减小sum的值，即将 right 向左移动
    	            right--;
    	        }
    	    }
    	    //数组 nums 中不存在和为 target 的两个数
    	    return new int[]{
        1, -1};
    	}
    }

（2）如果数组 nums 中可能有多对元素之和都等于 target，且题目要求变成返回所有和为 target 的元素对（不用考虑元素对的顺序），其中不能出现重复（例如 \[1, 3\] 和 \[3, 1\]就算重复）。解题的思路还是使用双指针，并且需要去掉重复的元素对。

**示例1：**  
输入：nums =\[4,4,2,6,3,3,8,0\], target = 8  
输出：\[0, 8\] \[2, 6\] \[4, 4\]

代码实现如下：

class Solution {
        
    	public List<List<Integer>> twoSum(int[] nums, int target) {
        
    	    //对数组进行排序
    	    Arrays.sort(nums);
    	    // res 用于存储结果
    	    List<List<Integer>> res = new ArrayList<>();
    	    //定义双指针
    	    int left = 0;
    	    int right = nums.length - 1;
    	    while (left < right) {
        
    	        int sum = nums[left] + nums[right];
    	        int leftVal = nums[left], rightVal = nums[right];
    	        if (sum == target) {
        
    	            //将找到的元素对保存起来
    	            res.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
    	            //跳过所有重复的元素
    	            while (left < right && nums[left] == leftVal) {
        
    	                left++;
    	            }
    	            while (left < right && nums[right] == rightVal) {
        
    	                right--;
    	            }
    	        } else if (sum < target) {
        
    	            //增大 sum 的值，即将 left 向右移动，同时跳过重复元素
    	            while (left < right && nums[left] == leftVal) {
        
    	                left++;
    	            }
    	        } else {
        
    	            //减小 sum 的值，即将 right 向左移动，同时跳过重复元素
    	            while (left < right && nums[right] == rightVal) {
        
    	                right--;
    	            }
    	        }
    	    }
    	    return res;
    	}
    }

[LeetCode_15.]: https://blog.csdn.net/weixin_43004044/article/details/118107655
[LeetCode_16.]: https://blog.csdn.net/weixin_43004044/article/details/118110152
[LeetCode_18.]: https://blog.csdn.net/weixin_43004044/article/details/118164049
[LeetCode_167._ II -]: https://blog.csdn.net/weixin_43004044/article/details/129296040
[LeetCode_454._ II]: https://blog.csdn.net/weixin_43004044/article/details/125439346