4Sum——LeetCode

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)

The solution set must not contain duplicate quadruplets.

 

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.



    A solution set is:

    (-1,  0, 0, 1)

    (-2, -1, 1, 2)

    (-2,  0, 0, 2)

제목 대의: 3 Sum 과 유사 합 니 다. 이 문 제 는 한 배열 에서 4 개의 수의 합 이 target 과 같은 것 을 찾 는 것 입 니 다. 만약 에 4. 567915 를 사용한다 면 복잡 도 는 O (N ^ 3) 가 되 고 효율 은 참 을 수 없습니다.
첫 번 째: 제 가 생각 한 첫 번 째 방법 은 a + b 의 합 을 매 거 진 다음 에 하나의 배열 을 넣 은 다음 에 이 배열 을 정렬 한 다음 에 Binary Search 로 target - c - d 가 이 배열 에 존재 하 는 지 찾 는 것 입 니 다. 여기 서 문 제 는 배열 이 a, b 의 하 표를 기록 하고 class 를 정의 하거나 2 차원 배열 만 할 수 있 습 니 다. 시간 복잡 복 은 O (N ^ 2 * logN) 입 니 다.
To add...
두 번 째: 나중에 생각 나 는 방법 은 매 거 진 a + b 의 합 을 HashMap 에 넣 고 a + b 의 합 을 key 로 하 는 것 입 니 다. 이 두 수의 아래 표 시 를 value 로 하 는 것 입 니 다. 평균 적 으로 분산 되면 이러한 시간 복잡 도 는 O (N ^ 2) 입 니 다. 최 악의 경 우 는 모든 숫자 가 같 습 니 다. 그러면 n ^ 2 개의 수 는 하나의 key 만 있 습 니 다. List 에 n ^ 2 개 와 O (N ^ 4) 로 퇴화 합 니 다.

    public List<List<Integer>> fourSum(int[] num, int target) {

        List<List<Integer>> res = new ArrayList<>();

        if (num == null || num.length < 4) {

            return res;

        }

        int len = num.length;

        Map<Integer, List<Integer>> map = new HashMap<>();

        Set<String> unique = new HashSet<>();

        for (int i = 0; i < len; i++) {

            for (int j = i + 1; j < len; j++) {

                int key = num[i] + num[j];

                if (map.get(key) == null) {

                    List<Integer> list = new ArrayList<>();

                    list.add(i * len + j);

                    map.put(key, list);

                } else {

                    List<Integer> list = map.get(key);

                    list.add(i * len + j);

                    map.put(key, list);

                }

            }

        }

        for (int i = 0; i < len; i++) {

            for (int j = i + 1; j < len; j++) {

                int key = target - num[i] - num[j];

                List<Integer> list = map.get(key);

                if (list == null || list.isEmpty()) {

                    continue;

                }

                for (Integer pos : list) {

                    int x = pos / len;

                    int y = pos % len;

                    if (i == x || i == y || j == x || j == y || x == y)

                        continue;

                    int[] t = new int[]{num[i], num[j], num[x], num[y]};

                    Arrays.sort(t);

                    String uni = String.valueOf(t[0]) + t[1] + t[2] + t[3];

                    if (!unique.contains(uni)) {

                        unique.add(uni);

                        res.add(Arrays.asList(t[0], t[1], t[2], t[3]));

                    }

                }

            }

        }

        return res;

    }