我有一个接受两个参数的方法。第一个是整数数组,第二个是整数。

该方法应打印索引对,其中这些索引中存在的值之和等于第二个输入参数。

蛮力方法是有两个循环,这将花费O(n ^ 2)时间。但是我需要在O(n)时间内解决此问题。

该数组可以有重复,也可以有负数。

如果打印一对,则不允许反向对。例如在下面的示例中,如果它不应该打印(4,0), (3,2), (5,3)

int[] arr = {3,4,-1,6,2,-1};
int sum = 5;


方法签名为:findPairs(int[] arr, int sum);

该方法的输出为:(0,4), (2,3), (3,5)

说明:

Element present at index 0 + Element present at index 4 = 3+2 = 5
Element present at index 2 + Element present at index 3 = -1+6 = 5
Element present at index 3 + Element present at index 5 = 6+-1 = 5


为了澄清一些混淆,我尝试使用HashMap<Integer, List<Integer>>。在这里,键是数组的元素,值是它们各自的索引。由于允许重复,因此对于给定元素,可以有多个索引位置。因此,地图中的值是一个列表。

最佳答案

您的方法是绝对正确的。

使用Map确实可以解决O(n)中的这个问题。

在这种情况下,我们将利用TreeMap来利用JAVA提供给我们的收益。 (不需要使用)。

而且,可以使用访问地图来解决最终答案中的重复索引对问题。这张地图检查我以前是否访问过特定索引。如果是,那么我不会在回答中包括它。

看一下下面的实现:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    private static SortedMap<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
    private static final Scanner scanner = new Scanner(System.in);

    String findPairs(int[] arr, int sum){

        for(int i=0;i<arr.length;i++){
            List<Integer> indexList = map.get(arr[i]);
            if(indexList == null){
                List<Integer> newIndexList = new ArrayList<Integer>();
                newIndexList.add(i);
                map.put(arr[i], newIndexList);
            }else{
                indexList.add(i);
            }
        }

        Set s = map.entrySet();

        HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();

        // Using iterator in SortedMap
        Iterator it = s.iterator();

        String finalOutput = "";

        while (it.hasNext())
        {
            Map.Entry m = (Map.Entry)it.next();

            int key = (Integer)m.getKey();
            List<Integer> indexList1 = (List<Integer>)m.getValue();

            if(map.containsKey(sum-key)){

                List<Integer> indexList2 = (List<Integer>)map.get(sum-key);

                for(int i=0;i<indexList1.size();i++){

                    if(!visited.containsKey(indexList1.get(i))){

                        for(int j=0;j<indexList2.size();j++){
                            if(!(finalOutput.equals("") || finalOutput==null)){
                                finalOutput += ", ";
                            }
                            finalOutput += "(" + indexList1.get(i) + "," + indexList2.get(j) + ")";
                            visited.put(indexList2.get(j), true);
                        }
                        visited.put(indexList1.get(i), true);
                    }
                }
            }
        }

        return finalOutput;
    }

    public static void main(String[] args) throws IOException {

        int[] arr = {3,4,-1,6,2,-1};
        int sum = 5;

        Solution obj = new Solution();

        System.out.println(obj.findPairs(arr, sum));
    }
}


请随时提出疑问。

09-10 05:10
查看更多