两数之和Ⅲ

无序 有重复数字 的 两数之和为 target 的两数下标

public class TwoSumⅢ {

    /**
     * 无序 有重复数字 的 两数之和为 target 的两数下标
     * @param args
     */
    private static final String delimiter = "-";
    public static void main(String[] args) {
        // 1, 6, 5, 3, 1, 3, 5, 4, 6
        // 0, 0, 0, 0, 0, 0, 0, 0, 0
        List<List<String>> res = twoSumⅢ(10, new int[]{1, 6, 5, 3, 1, 3, 5, 4, 6});

        for (List<String> val : res) {
            System.out.println(val + " ");
        }
    }

    public static List<List<String>> twoSumⅢ(int target, int[] arr) {
        List<List<String>> res = new LinkedList<>();
        // key: 值 value: index...
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++){
            if (!map.containsKey(arr[i])){
                map.put(arr[i], i + "");
            }else {
                //String[] vals = map.get(arr[i]).split(delimiter);
                String val = map.get(arr[i]);
                map.put(arr[i], val + delimiter + i);
            }
        }
        // 排序
        Arrays.sort(arr);

        // 双指针
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int leftVal = arr[left], rightVal = arr[right];
            if (arr[left] + arr[right] > target) {
                right--;
            } else if (arr[left] + arr[right] < target) {
                left++;
            } else {
                // 获取下标
                String[] vals0 = map.get(arr[left]).split(delimiter);
                String[] vals1 = map.get(arr[right]).split(delimiter);
                // 笛卡尔积处理
                int t = 0;
                for (int i = 0; i < vals0.length; i++) {
                    // 如果是同一个对象 不做笛卡尔积
                    if (map.get(arr[left]) == map.get(arr[right])) t = i + 1;
                    for (int j = t; j < vals1.length; j++) {
                        if (vals0[i].equals(vals1[j])) continue;   // 去重
                        List<String> partRes = new LinkedList<>();
                        partRes.add(vals0[i]);
                        partRes.add(vals1[j]);
                        res.add(partRes);
                    }
                }
                // 跳过所有相同的值
                while(left < right && leftVal == arr[left]) left++;
                while(left < right && rightVal == arr[right]) right--;
            }
        }
        return res;
    }
}