Реализация 4sum в Java от Leetcode

Формулировка проблемы из 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.

Замечания:

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.

Об этой проблеме четырех сумм у меня есть 2 вопроса:

Where I went wrong? The compiled code cannot pass all the tests, but I thought the code should be right since it is only using brute force to solve the problem. Is there any efficient way to solve the four sum problem instead of this O(n^4) run-time algorithm?
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class FourSumSolution{
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target){
        ArrayList<ArrayList<Integer>> aList = new ArrayList<ArrayList<Integer>>();
        int N = num.length;

        for(int i=0; i<N; i++)
            for(int j=i+1; j<N; j++)
                for(int k=j+1; k<N; k++)
                    for(int l=k+1; l<N; l++){
                        int sum = num[i] + num[j] + num[k] + num[l];                        
                        if(sum == target){
                            ArrayList<Integer> tempArray = new ArrayList<Integer>();
                            Collections.addAll(tempArray, num[i], num[j], num[k], num[l]);
                            aList.add(tempArray);
                        }
                    }
        return aList;   
    }
}
 Gene27 июн. 2012 г., 00:13
Вам необходимо предоставить ссылку на проблему.
 assylias27 июн. 2012 г., 00:08
 dann.dev27 июн. 2012 г., 00:04
Вероятно, вам следует подробнее рассказать о первоначальной проблеме, некоторые люди могут подумать, что четыре суммы относятся к чему-то еще ...
 lxx2202 июл. 2012 г., 07:30
Джину и Dann.dev, большое спасибо. Я отредактировал пост, и ссылкаleetcode.com/onlinejudge, Проблема в 4сум. Большое спасибо.
 Dave Newton27 июн. 2012 г., 00:04
Я предпочитаю три.

Ответы на вопрос(5)

очевидно, рассчитывается правильно. Но если значение появляется несколько раз во входном массиве, ему будет дано "то же самое" Результаты. Может быть, это было проверено.

& Quot; TwoSum & quot; из числа = {1, 3, 1, 3, 4} с целью = 4 будет:

{ 1, 3 } { 1, 3 } { 3, 1 } { 1, 3 }

Если бы это было причиной неудачи в тестах, решение, вероятно, было быa set of an ordered list.

Если также должны быть заданы подмножества, {4} отсутствует.

So the question is, why did the tests fail, what are the requirements.

Оптимизация, вероятно, включает в себя специальные структуры данных: по крайней мере (обратный) отсортированный номер. Многие ссылки уже даны. Рекурсия может помочь найтиprovable и понятное оптимальное решение с предварительными и последующими условиями. (Как вы разделяете проблему.)

Одним из решений было бы создание пар, сохраняющих отображение парной суммы на все пары индексов, ведущих к этой сумме. А потом найдите две пары с несвязанными индексами.

As no one gave a satisfactory answer:

Простое рекурсивное решение (не очень хорошее или оптимальное). Однако это демонстрирует, что структуры данных имеют отношение.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;

public class FourSumSolution {

    private static class SortedTuple implements Comparable<SortedTuple> {
        int[] values;

        public SortedTuple(int... values) {
            this.values = Arrays.copyOf(values, values.length);
            Arrays.sort(this.values);
        }

        public int size() {
            return values.length;
        }

        public int get(int index) {
            return values[index];
        }

        public ArrayList<Integer> asList() {
            // Result type is ArrayList and not the better List,
            // because of the external API of the outer class.
            ArrayList<Integer> list = new ArrayList<Integer>(values.length);
            for (int value: values)
                list.add(value);
            return list;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + Arrays.hashCode(values);
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            SortedTuple other = (SortedTuple) obj;
            if (!Arrays.equals(values, other.values))
                return false;
            return true;
        }

        @Override
        public int compareTo(SortedTuple other) {
            int c = cmp(values.length, other.values.length);
            if (c == 0) {
                for (int i = 0; i < values.length; ++i) {
                    c = cmp(values[i], other.values[i]);
                    if (c != 0)
                        break;
                }
            }
            return c;
        }

        @Override
        public String toString() {
            return Arrays.toString(values);
        }

        private static int cmp(int lhs, int rhs) {
            return lhs < rhs ? -1 : lhs > rhs ? 1 : 0; // Cannot overflow like lhs - rhs.
        }
    }

    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        final int nTerms = 4;
        SortedTuple values = new SortedTuple(num);
        SortedSet<SortedTuple> results = new TreeSet<SortedTuple>();
        int[] candidateTerms = new int[nTerms];
        int valuesCount = values.size();
        solveNSum(target, nTerms, values, results, candidateTerms, valuesCount);

        ArrayList<ArrayList<Integer>> aList = new ArrayList<ArrayList<Integer>>();
        for (SortedTuple solution: results) {
            aList.add(solution.asList());
        }
        return aList;   
    }

    public static void main(String[] args) {
        final int[] num = { 1, 3, 1, 3, 4 };
        final int requiredSum = 4;
        final int nTerms = 2;

        SortedTuple values = new SortedTuple(num);
        SortedSet<SortedTuple> results = new TreeSet<SortedTuple>();
        int[] candidateTerms = new int[nTerms];
        int valuesCount = values.size();
        solveNSum(requiredSum, nTerms, values, results, candidateTerms, valuesCount);

        System.out.println("Solutions:");
        for (SortedTuple solution: results) {
            System.out.println("Solution: " + solution);
        }
        System.out.println("End of solutions.");
    }

    private static void solveNSum(int requiredSum, int nTerms, SortedTuple values, SortedSet<SortedTuple> results, int[] candidateTerms, int valuesCount) {
        if (nTerms <= 0) {
            if (requiredSum == 0)
                results.add(new SortedTuple(candidateTerms));
            return;
        }
        if (valuesCount <= 0) {
            return;
        }

        --valuesCount;
        int candidateTerm = values.get(valuesCount);

        // Try with candidate term:
        candidateTerms[nTerms - 1] = candidateTerm;
        solveNSum(requiredSum - candidateTerm, nTerms - 1, values, results, candidateTerms, valuesCount);

        // Try without candidate term:
        solveNSum(requiredSum, nTerms, values, results, candidateTerms, valuesCount);
    }
}

Можно обрезать это дальше:

Skip the candidate term if the (nTerms - 1) lowest plus the candidate terms give a too large sum; terminate if the candidate term plus the next (nTerms -1) terms are too small. terminate if valuesCount < nTerms
 02 июл. 2012 г., 13:04
Приложил усилия, чтобы превратить мою "Blabla" на структурах данных в исполняемый код.
 lxx2202 июл. 2012 г., 07:30
Учитывая массив S из n целых чисел, существуют ли элементы a, b, c и d в S такие, что a + b + c + d = target? Найти все уникальные четверки в массиве, который дает сумму цели. Примечание. Требование гласит: «Набор решений не должен содержать повторяющиеся четверки».
Решение Вопроса

import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashSet;
public class Solution {
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    // Start typing your Java solution below
    // DO NOT write main() function

    Arrays.sort(num);
    HashSet<ArrayList<Integer>> hSet = new HashSet<ArrayList<Integer>>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < num.length; i++) {
        for (int j = i + 1; j < num.length; j++) {
            for (int k = j + 1, l = num.length - 1; k < l;) {
                int sum = num[i] + num[j] + num[k] + num[l];
                if (sum > target) {
                    l--;
                }
                else if (sum < target) {
                    k++;
                }
                else if (sum == target) {
                    ArrayList<Integer> found = new ArrayList<Integer>();
                    found.add(num[i]);
                    found.add(num[j]);
                    found.add(num[k]);
                    found.add(num[l]);
                    if (!hSet.contains(found)) {
                        hSet.add(found);
                        result.add(found);
                    }

                    k++;
                    l--;

                }
            }
        }
    }
    return result;
}

}

которое не использует хэш. Это должно быть быстрее, но все равно превышает лимит времени.

import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {

      int[] S = {1, 0, -1, 0, -2, 2};
      int target = 0;
      test(S, target);
    }

    public static void test(int[] num, int target) {
      System.out.print("a:");
      for (int i : num) {
        System.out.print(" " + i);
      }
      System.out.println(": " + target);
      ArrayList<ArrayList<Integer>> res = fourSum(num, target);
      for (ArrayList<Integer> list : res) {
        System.out.println(list);
      }
      System.out.println();
    }

    // a+b+c+d = target
    public static ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function

       // Sort
       {
        for (int i = 0; i < num.length; i++) {
            for (int j = i + 1; j < num.length; j++) {
                if (num[j] < num[i]) {
                    int tmp = num[i];
                    num[i] = num[j];
                    num[j] = tmp;
                }
            }
        }
       }
      ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
      int i = 0;
      while (i < num.length - 3) {
        int j = i + 1;
        while (j < num.length - 2) {
            int k = j + 1, l = num.length - 1;
            while (k < l) {
                int sum = num[i] + num[j] + num[k] + num[l];
                if (sum > target) {
                    l--;
                    while (k < l && num[l] == num[l+1]) l--;
                } else if (sum < target) {
                    k++;
                    while (k < l && num[k] == num[k-1]) k++;
                } else {
                    ArrayList<Integer> list =
                        new ArrayList<Integer>(4);
                    list.add(num[i]); list.add(num[j]);
                    list.add(num[k]); list.add(num[l]);
                    res.add(list);
                    k++;
                    while (k < l && num[k] == num[k-1]) k++;
                    l--;
                    while (k < l && num[l] == num[l+1]) l--;
                }
            }
            j++;
            while (j < num.length && num[j] == num[j-1]) j++;
        }
        i++;
        while (i < num.length && num[i] == num[i-1]) {
            i++;
        }
      }

      return res;
    }
}
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    Arrays.sort(num);
    ArrayList<ArrayList<Integer>> res=new ArrayLi,st<ArrayList<Integer>>();
    int i=0;
    while(i<num.length-3){
        int j=i+1;
        while(j<num.length-2){
            int left=j+1, right=num.length-1;
            while(left<right){
                if(num[left]+num[right]==target-num[i]-num[j]){
                    ArrayList<Integer> t=new ArrayList<Integer>();
                    t.add(num[i]);
                    t.add(num[j]);
                    t.add(num[left]);
                    t.add(num[right]);
                    res.add(t);
                    left++;
                    right--;
                    while(left<right && num[left]==num[left-1])
                        left++;
                    while(left<right && num[right]==num[right+1])
                        right--;
                }else if(num[left]+num[right]>target-num[i]-num[j])
                    right--;
                else
                    left++;
            }
            j++;
            while(j<num.length-2 && num[j]==num[j-1])
                j++;
        }
        i++;
        while(i<num.length-3 && num[i]==num[i-1])
            i++;
    }
    return res;
}
 08 янв. 2014 г., 23:57
Добро пожаловать на ТАК! Ответы только на код часто здесь не одобряются. Пожалуйста, добавьте описаниеwhy этот ответ правильный и что вы изменили, чтобы заставить его работать.

private static int countFourSum(int[] numbers) {
    int count = 0;
    for (int j = 0; j < numbers.length; j++) {
        for (int i = j + 1; i < numbers.length; i++) {
            int front = i + 1, rear = numbers.length - 1;

            while (front < rear) {
                if (numbers[front] + numbers[rear] + numbers[i] + numbers[j] == 0) {
                    System.out.printf(String.format("{%d} : {%d} : {%d} : {%d}  \n", numbers[front], numbers[rear],
                            numbers[j], numbers[i]));
                    front++;
                    rear--;
                    count++;
                } else {
                    if (Math.abs(numbers[front]) > Math.abs(numbers[rear])) {
                        front++;
                    } else {
                        rear--;
                    }
                }
            }
        }

    }
    return count;
}

public static void main(String[] args) {
    int[] numbers = { 1, 2, 3, 4, -4, -5, -6, 2, 4, -1 };
    Arrays.sort(numbers);
    System.out.println(countFourSum(numbers));
}

}

Ваш ответ на вопрос