3SUM，但允许重复

Question

我正在尝试解决 3SUM Problem，但允许重复的三元组。例如，假设我们有数组 [2 0 -1 1 -2 3 3]。在这里，解决方案是 (2, 0, -2)、(0, -1, 1)、(-1, -2, 3) 和 (-1, -2, 3)。解决方案也可以视为 (A[0], A[1], A[4]), (A[1], A[2], A[3]), (A[2], A[4 ]、A[5]）和（A[2]、A[4]、A[6]）。索引必须是唯一的组合，但如果它们是相同的值就可以了。

阅读该问题后，我找到了很多关于避免重复的解决方案，但 none 却没有保留它们。我将如何在不避免重复的情况下实施该问题？

我正在寻找 O(N^2) 的解决方案或 O(N^2logN) 的解决方案（不是蛮力！）

Answer 1

首先对数组进行排序。
做一个嵌套循环。
外循环从 0 到 n-2
内循环从i+1到n-1（这里，i是外循环的迭代变量）。
现在，我们通过将 i 和 j 索引的值相加得到两个总和值。
我们检查 -two_sum 以获得总和为 0 的三元组。
我们进行一些预处理并收集所有值及其在哈希图中的索引。
现在，我们可以简单地检查它是否存在，并通过遍历存储在 map 中的索引来添加所有三元组。
时间复杂度：O(n^2)（不包括添加三元组循环）。

片段：

import java.util.*;
class Main {
    public static List<List<Integer>> threeSum(int[] nums) {      
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        Map<Integer,LinkedList<Integer>> map = new HashMap<Integer,LinkedList<Integer>>();

        for(int i=0;i<nums.length;++i){
            if(!map.containsKey(nums[i])) map.put(nums[i],new LinkedList<Integer>());
            map.get(nums[i]).add(i);
        }

        for(int i=0;i<nums.length-2;++i){
           map.get(nums[i]).poll();
            for(int j=i+1;j<nums.length-1;++j){
               map.get(nums[j]).poll();
               int search_value = -(nums[i] + nums[j]);
               if(map.containsKey(search_value) && map.get(search_value).size() > 0){
                   int start_index = map.get(search_value).peek();
                   int end_index = map.get(search_value).peekLast();
                   for(int k = start_index;k <= end_index;++k) res.add(Arrays.asList(nums[i],nums[j],nums[k])); // add all triplets
               }
            }

            // restore all popped items
            for(int j=nums.length-2;j>i;--j){
                map.get(nums[j]).addFirst(j);
            }

            if(map.get(nums[i]).size() == 0) map.remove(nums[i]);
        }        

        return res;
    }

    public static void main(String... args){
        List<List<Integer>> triplets = threeSum(new int[]{2,0,-1,1,-2,3,3});
        for(int i=0;i<triplets.size();++i) System.out.println(triplets.get(i).toString());
    }

}

演示： https://onlinegdb.com/SJ4ALZ7bL

3SUM，但允许重复

3SUM, but duplicates allowed

language-agnostic

arrays

algorithm

indexing

combinations