作者 | 小灰
来源 | 程序员小灰（ID：chengxuyuanxiaohui）
————— 第二天 —————
什么意思呢？我们来举个例子，给定下面这样一个整型数组（题目假定数组不存在重复元素）：
我们随意选择一个特定值，比如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; }
更多精彩推荐
☞2020互联网公司中秋礼盒大比拼！（文末送福利）
☞糟糕，Windows XP 源代码泄漏……| 每日趣闻
☞错过了秋天的第一杯奶茶，不要错过秋天第一场黑客松
☞面向隐私AI的TensorFlow深度定制化实践
☞干货！一文看Doris在作业帮实时数仓中的应用&实践
☞DeFi深陷大规模“走出去”困境？Wing祭出三大杀手锏
点分享点点赞点在看
