3-和算法分析

Question

我知道解决三和问题的两种方法。

问题陈述：

给定n个整数的数组S，S中是否有元素a，b，c使得a+b+c= 0？在数组中找到所有唯一的三重奏，这会给出零的和。

Solution1:使用2指针方法的

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    if (nums == null || nums.length < 3)
        return result;

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        if (i == 0 || nums[i] > nums[i - 1]) {
            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> l = new ArrayList<Integer>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    result.add(l);

                    j++;
                    k--;

                    //handle duplicate here
                    while (j < k && nums[j] == nums[j - 1])
                        j++;
                    while (j < k && nums[k] == nums[k + 1])
                        k--;

                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }

    }

    return result;
}

Solution2:使用地图的

public List<List<Integer>> threeSum(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();
    HashMap<String, Integer> map2 = new HashMap<>();
    List<List<Integer>> list = new LinkedList<>();
    for (int i : nums) {
        map.put(i, map.get(i) != null ? map.get(i) + 1 : 1);
    }
    for (int i = 0; i < nums.length - 2; i++) {
        for (int j = i + 1; j < nums.length - 1; j++) {
            int findMe = -(nums[i] + nums[j]);
            Integer count = map.get(findMe);
            if (count != null) {
                if ((count == 1 && nums[i] != findMe && nums[j] != findMe) || (count == 2 && (nums[i]!=nums[j] || nums[j]!=findMe)) || count > 2) {
                    int min = Math.min(findMe, Math.min(nums[i], nums[j]));
                    int max = Math.max(findMe, Math.max(nums[i], nums[j]));
                    if (map2.get(min + "" + max) == null) {
                        map2.put(min + "" + max, max);
                        LinkedList<Integer> li = new LinkedList<>();
                        li.add(min);
                        li.add(-(min + max));
                        li.add(max);
                        list.add(li);
                    }
                }
            }

        }
    }
    return list;
}

上下文：

1)Solution1 --解的时间复杂度为-> O(nlogn) + O(n^2) ~ O(n^2)

2)Solution2 --解的时间复杂度为-> O(n) + O(n^2) + O(k) ~ O(n^2)

我的问题：都是O(n^2)算法。然而，对于较大的输入，Solution1的性能优于2，但是根据时间复杂性分析，Solution2应该执行得更好。有人能帮我理解一下为什么会这样吗？

我正在使用的输入：

[13,14,1,2,-11,-11,-1,5,-1,-11,-9,-12,5,-3,-7,-4,-12,-9,8,-13,-8,2,-6,8,11,7,7,-6,8,-9,0,6,13,-14,-15,9,12,-9,-9,-4,-4,-3,-9,-14,9,-8,-11,13,-10,13,-15,-11,0,-14,5,-4,0,-3,-3,-7,-4,12,14,-14,5,7,10,-5,13,-14,-2,-6,-9,5,-12,7,4,-8,5,1,-10,-3,5,6,-9,-5,9,6,0,14,-15,11,11,6,4,-6,-10,-1,4,-11,-8,-13,-10,-2,-1,-7,-9,10,-7,3,-4,-2,8,-13]

Answer 1

你应该明白，渐近分析并没有给出精确的时间或空间复杂性。

然而，您正在测量这两个解决方案的确切时间。

来问一下您的问题，当输入很大时，在solution2中O(k)正在变得越来越大，这就是为什么计算solution2所用的时间比solution1要多。