# 算法讨论题 —— Java实现两数之和

**URL:** <https://www.isharkfly.com/t/java/14998>\
**Category:** 职友\
**Tags:** oa, 面经, java\
**Created:** [September 20, 2023, 1:55pm UTC](https://www.isharkfly.com/t/java/14998 "2023-09-20T13:55:01Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![honeymoose](https://www.isharkfly.com/user_avatar/www.isharkfly.com/honeymoose/32/20796_2.png) [@honeymoose](https://www.isharkfly.com/u/honeymoose)\
**Post date:** [September 20, 2023, 1:55pm UTC](https://www.isharkfly.com/t/java/14998/1 "2023-09-20T13:55:01Z")

</div>

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。即:每个index上的数字只能用一次。

 ![2023-09-20_14-03-08](https://cdn.isharkfly.com/com-isharkfly-www/discourse-uploads/original/2X/0/068427f9c596f25b5f4181b6c48393b43dff62ce.png)

## 示例

给定 nums = [2, 7, 11, 15], target = 9  
因为 nums[0] + nums[1] = 2 + 7 = 9  
所以返回 [0, 1]

## 解答

这个题目的原题是在：[https://leetcode.cn/problems/two-sum/description/](https://leetcode.cn/problems/two-sum/description/) 网站上能找到。

```auto
给定一个整数数组 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
只会存在一个有效答案
 

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

```

完整的题目要求如上。

应该对所有人第一次想到的就是使用 2 个 For 循环吧。

```auto
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    log.debug("{}", new int[]{i, j});
                }
            }
        }

```

然后从 2 个 for 循环中获得下标列表，最后 break 循环就可以了。

### 进阶问题

如何让我们只使用 1 个 for 循环的情况下解决这个问题。

这个时候我们就需要使用 HashMap 了。

首先，我们把数据放入到 HashMap 中。

然后取第一个元素，当取得第一个元素后，再用和减去第一个元素，这个得到的值为另外一个元素。

然后拿着这个元素到 HasMap 中去找，如果找到了就返回，如果没找到就继续去获得下一个元素。

然后再拿和去减去获得的第二个元素后再到 Map 中去找。

```auto
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                log.debug("{}", new int[]{i, map.get(complement)});
            }
        }

```

### 用一个 Map 解决

还有一个更高的效率，就是在循环一次，然后用 Map 解决。

在上面的解决方案中，我们在对 HashMap 遍历了 2 次，第一次是构建 Map，第二次是从 Map 中查找。

能不能我们在构建的时候就完成操作。

答案是肯定的。

于是，我们就有了下面的代码：

```auto
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {

            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                log.debug("{}", new int[]{map2.get(complement), i});
            }
            map2.put(nums[i], i);
        }

```

上面的代码在 HashMap 构建的时候就进行判断，把和减掉当前的值，如果我们的 Map 中能够找到这个值，我们就返回。

如果不能找到就添加到 Map 中。

## 总结

如果不考虑效率的方法，第一个方法就可以解决问题了。

这个没有什么难度。

如果需要考虑效率的话，重构数据结构，通常是比较有效的方法，Java 中用得比较多的是 Map，因为 Map 通常能够存储更多的信息，而且遍历效率高。

我们对一些问题，如果算法不太好弄的话，通常考虑的是能不能给它们换个数据结构，比如说 List ，Map 呀这种的。

个人感觉这个题目在算法中是属于比较简单的题目，但是不同的解法可能会比较多。

整体感觉还是不错的，没有像一些算法题目，一上来就给你一个下马威，你完全都没有想明白数据结构应该怎么存。然后后面的逻辑就会越来越混乱。