1:找到其中的一組
將數(shù)組中的所有的值放入HashMap的Key中，Value存放該值對應(yīng)的下標势告，遍歷這個HashMap抚恒，取得Key俭驮，計算如果可以和這個Key加起來的和為num的值，如果這個值存在遗遵，就直接返回這兩個下標逸嘀。遍歷一次的時間復(fù)雜度為O(N)，查找的時間復(fù)雜度是O(1)翼岁，總體時間復(fù)雜度O(N)司光。
private static void findTwoTotalNumber(int[] array, int number) {
if (array == null || array.length <= 1) {
return;
}
HashMap<Integer, Integer> hashMap = new HashMap<>();
int index = 0;
for (int num: array) {
hashMap.put(num, index++);
}
for (Integer num: hashMap.keySet()) {
if (hashMap.containsKey(number - num)) {
System.out.println("one is;" + num +"--index==" + hashMap.get(num) +"--other is:"
+ (number - num) + "--index is ==" + hashMap.get(number - num));
return;
}
}
}
思路解析
1：將數(shù)組中的元素存儲在hashmap中残家，其中key為數(shù)組的元素坞淮，value為其在數(shù)組的下標
2：遍歷整個hashmap, 如果hashmap的key中包括(total - curNum)，那么說明數(shù)組中存在另外一個數(shù)滿足和當(dāng)前數(shù)相加為total的元素晃跺，那么直接打印出來即可
問題：
上面的做法只能找到一組滿足條件的組合毫玖，實際情況是可能有多組，那么我們看下多組的實現(xiàn)方式
2:找到滿足所有的組合
private static void findTwoNumberTotal(int[] array, int total) {
if (array == null || array.length <= 1) {
return;
}
/* 組合數(shù)的下標烹玉，key和value */
HashMap<Integer, Integer> hashMap = new HashMap<>();
/*已經(jīng)遍歷過的數(shù)據(jù) */
HashMap<Integer, Integer> valueHashMap = new HashMap<>();
int temp = 0;
for (int i = 0; i < array.length; i++) {
temp = total - array[i];
if (valueHashMap.containsKey(temp)) {------>如果包含另外一個組合數(shù)
//valueHashMap.get(temp)得到的是另外一個組合數(shù)的下標
//hashmap存儲的是兩個組合數(shù)的下標
hashMap.put(valueHashMap.get(temp), i);
continue;
}
valueHashMap.put(array[i], i);------>將數(shù)組的元素按照值和在數(shù)組對應(yīng)的下標存儲
}
valueHashMap = null;
for (int key : hashMap.keySet()) {
//因為hashmap的key是一個組合數(shù)的下標二打，value是另外一個組合數(shù)的下標
System.out.println(array[key] + " " + array[hashMap.get(key)]);
}
}
