漫画：如何在数组中找到和为 “特定值” 的两个数？
时间：2020-09-28 14:00:47
手机看文章
扫描二维码
随时随地手机看文章
[导读]一组漫画告诉你！
————— 第二天 —————
什么意思呢？我们来举个例子，给定下面这样一个整型数组（题目假定数组不存在重复元素）：
我们随意选择一个特定值，比如13，要求找出两数之和等于13的全部组合。
由于12+1 = 13，6+7 = 13，所以最终的输出结果（输出的是下标）如下：
【1， 6】
【2， 7】
小灰想表达的思路，是直接遍历整个数组，每遍历到一个元素，就和其他元素相加，看看和是不是等于那个特定值。
第1轮，用元素5和其他元素相加：
没有找到符合要求的两个元素。
第2轮，用元素12和其他元素相加：
发现12和1相加的结果是13，符合要求。
按照这个思路，一直遍历完整个数组。
————————————
让我们来具体演示一下：
第1轮，访问元素5，计算出13-5=8。在哈希表中查找8，发现查不到：
第2轮，访问元素12，计算出13-12=1。在哈希表中查找1，查到了元素1的下标是6，所以元素12（下标是1）和元素1（下标是6）是一对结果：
第3轮，访问元素6，计算出13-6=7。在哈希表中查找7，查到了元素7的下标是7，所以元素6（下标是2）和元素7（下标是7）是一对结果：
按照这个思路，一直遍历完整个数组即可。
public class FindSumNumbers {
public static List> twoSum(int[] nums, int target) {
Map map = new HashMap<>();
List> resultList = new ArrayList<>();
for (int i = 1; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int other = target - nums[i];
if (map.containsKey(other) && map.get(other) != i) {
resultList.add(Arrays.asList(i,map.get(other)));
//为防止找到重复的元素对，匹配后从哈希表删除对应元素
map.remove(nums[i]);
}
}
return resultList;
}
public static void main(String[] args) {
int[] nums = {5,12,6,3,9,2,1,7};
List> resultList = twoSum(nums, 13);
for(List list : resultList){
System.out.println(Arrays.toString(list.toArray()));
}
}
}
public static List> twoSumV2(int[] nums, int target) {
Map map = new HashMap<>();
List> resultList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int other = target - nums[i];
if (map.containsKey(other)) {
resultList.add(Arrays.asList(map.get(other),i));
}
map.put(nums[i], i);
}
return resultList;
} 中秋节快要到了，小灰给大家准备了一个福利，
扫码关注下方公众号，回复关键字“奶茶”，可以参与抽奖：
点个[在看]，是对小灰最大的支持！
免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！
下载文档
