侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 102 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

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

惊羽
2021-06-19 / 0 评论 / 0 点赞 / 157 阅读 / 1,661 字
温馨提示:
本文为原创作品,感谢您喜欢~

题目

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

评论区