0
\$\begingroup\$

I have 2 solutions about puzzle I mentioned in title:

solution 1( O(n^3) ):

public static boolean sumOfThree_1(List<Integer> list, int sum) {
        for (int i = 0; i < list.size() - 2; i++) {
            for (int k = i + 1; k < list.size() - 1; k++) {
                for (int m = k + 1; m < list.size(); m++)
                    if ((list.get(i) + list.get(k) + list.get(m)) == sum) {
                        return true;
                    }
            }
        }
        return false;
    }

solution 2( O(n^2) ):

public static boolean sumOfThree_2(List<Integer> list, int sum) {
        for (int i = 0; i < list.size() - 2; i++) {
            int expectedSumOfTwo = sum - list.get(i);
            if (sumOfTwo_2(list.subList(i+1, list.size()), expectedSumOfTwo)) {
                return true;
            }
        }
        return false;
    }

public static boolean sumOfTwo_2(List<Integer> list, int sum) {
    Set<Integer> set = new HashSet<>();
    for (int element : list) {
        if (set.contains(sum - element)) {
            return true;
        }
        set.add(element);
    }
    return false;
}

Any suggestions about solutions?

Better solutions?

\$\endgroup\$
  • \$\begingroup\$ This looks to be a variation of the 3SUM problem, which you can read more about on the Wikipedia page. \$\endgroup\$ – Michael Fitzpatrick Oct 21 '18 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.