【算法学习】【数组】两数之和等于K

46 阅读 0 评论 31 点赞

我是靠谱客的博主虚拟咖啡豆，最近开发中收集的这篇文章主要介绍【算法学习】【数组】两数之和等于K，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在给定递增数组内，找到和为K的两个数字的下标，假设有且仅有唯一的一对数字，同一个数字仅使用一次。

作为一个刚开始研究算法的小白，说实话，我第一反应就是遍历然后依次匹配比较 ^_^

其实针对于数组这个类型的题目，都可以套用【双端指针】这个思路。

有这么几个关键词可以拿来做文章

和为K ，则两个【索引】映射的数组元素之和为K，本质是两个端点的索引。
递增数组，在和为K的前提下。会出现两种情况

1）和小于K，我们可以将较小的数变大，即头指针向右移动

2）和大于K，我们可以将较大的数变小，即尾指针向左移动

根据以上分析，代码如下，时间复杂度O(N)


public class Sum {
public static void main(String[] args) {
int k = 3;
int[] num = {1,2,4,6,10};
int[] result = index(num, k);
for (int value : result) {
System.out.println(value);
}
}
public static int[] index(int[] array,int target){
int idxStart = 0;
int idxEnd = array.length-1;
while (idxStart < idxEnd && array[idxStart]+array[idxEnd]!=target){
if(array[idxStart]+array[idxEnd]<target){
idxStart = idxStart+1;
}else {
idxEnd = idxEnd -1 ;
}
}
return new int []{idxStart,idxEnd};
}
}

现在时间是2022年1月6日，上文提到思路有问题，缺陷在于双指针来控制和的大小方案只适用于正整数，对于负整数来说，效果恰恰是相反的￣□￣｜｜这很尴尬呀，所以在这里更新一下算法，使用了哈希的思路


public static int[] index(int[] array,int target){
//key：value in array；value：index in array
Map<Integer,Integer> map = new HashMap<>(array.length);
for (int i = 0; i < array.length; i++) {
//计算预期差值
int perfect = target - array[i];
if (map.containsKey(perfect)){
return new int []{map.get(perfect),i};
}else {
map.put(array[i],i);
}
}
return null;
}