算法练习(9) - TwoSum问题变换

题目

有一个数组[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);
    }
}