有一个数组[1,2,5,7,8,8,9,4,4,6],求元素 m+n = 12 的组合,将所有的 m n 组合下标打印出来,需要过滤下标重复的组合,例如 4,7 7,4 是重复组合;时间复杂度需要是 O(n)
下面解法复杂度在 O(n) 到O(n方) 之间,不太符合要求,但没看到好解法,先这样吧
public class TwoSumTest {
@Test
public void twoSum_test() {
int[] arr = {1,2,5,7,8,8,9,4,4,6};
twoSum(arr,12);
}
private void twoSum(int[] arr, int target) {
HashMap<Integer,List<Integer>> map = new HashMap<>();
List<HashMap<Integer,Integer>> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if(map.get(target - arr[i]) == null){
List<Integer> list1 = new ArrayList<>();
map.put(target - arr[i],list1);
}
map.get(target - arr[i]).add(i);
}
HashMap<String,Boolean> map2 = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if(map.containsKey(arr[i])){
List<Integer> endList = map.get(arr[i]);
for (Integer is : endList) {
int front = i;
int end = is;
if(front == end){
continue;
}
if(front > end){
int temps = front;
front = end;
end = temps;
}
String key = front + "-" + end;
if(map2.get(key) == null){
HashMap<Integer,Integer> temp = new HashMap<>();
temp.put(front,end);
list.add(temp);
}
map2.put(key,true);
}
}
}
System.out.println(list);
}
}