Превышен лимит времени LeetCode 3Sum

Question

Итак, я пытаюсь решить проблему 3Sum в Leetcode. Мое решение получает правильный ответ, однако с более длинными тестами я получаю «Превышен лимит времени». Я предполагаю, что это из-за вложенных циклов for, которые я использую, но я не уверен, что делать дальше.

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
    int x = 0;
    int y = 0;
    int z = 0;
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();


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

    for (int i = 0; i < nums.length; i++){
        map.put(i, nums[i]);
    }

    for (int j = 0; j < nums.length - 2; j++){
        x = map.get(j);
        for(int k = j+1;k < nums.length - 1; k++){
            y = map.get(k);
            for(int l = k+1; l <nums.length; l++){
                z = map.get(l);
                if((x + y + z) == 0){
                    List<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(x);
                    triplet.add(y);
                    triplet.add(z);
                    System.out.println(triplet);
                    if (!(res.contains(triplet))){
                        res.add(triplet);
                    }

                }
            }
        }
    }
    return res;
}

Какие-либо советы о том, как оптимизировать это решение?

Answer 1

Ваше решение - O (N ^ 3). Следовательно, получение превышения лимита времени.

Вопрос может быть решен более эффективно, как показано ниже:

public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}