两数之和（暴力解法+优化）

这题目有点奇怪，我们都知道数组元素下标是从0开始的。它题目应该返回1，2，才是代表2+4=6，不管那么多，明白它需求的意思就开始分析思路
思路很简单：
（1）循环遍历所有元素
（2）拿着每一元素与目标值做差
（3）在剩余的元素里面找是否有刚好等于那个差值的
（4）记录两个下标返回
（5）如果不存在，返回null

public static void main(String[] args) {
int[] array = new int[]{3,2,4,5};
int[] result = twoSum(array, 5);
System.out.println(Arrays.toString(result));
}
private static int[] twoSum(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
int gap = target - array[i];
for (int k = array.length - 1; k > i; k--) {
if (array[k] == gap){
return new int[]{i,k};
}
}
}
return null;
}

target是5

target换成6

可见上面的解法没有问题，但是时间复杂度不是最优秀，执行效率不高，下面思考如何只使用一层循环来完成求和：

思路讲解：每一个元素跟目标值都会有一个差值，那么我们就先计算出这个差值，把差值作为key，当前元素的下标作为value存在一个Map中，等循环到array[i]元素恰好是差值的时候，就直接返回两个下标。

private static int[] twoSumPlus(int[] array, int target) {
// 更高效率的升级版
Map<Integer,Integer> map = new HashMap<>(array.length);
for (int i = 0; i < array.length; i++) {
// 计算出当前i差多少达到target
int gap = target - array[i];
// 如果map中刚好有那个差值，直接返回
if (map.get(array[i])!=null){
return new int[]{map.get(array[i]), i};
}
map.put(gap,i);
}
return null;
}

看下结果，输入目标值 8

最后

以上就是发嗲唇彩为你收集整理的两数之和（暴力解法+优化）的全部内容，希望文章能够帮你解决两数之和（暴力解法+优化）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。