时间戳

首页 > 解决方案 > 在数组中查找值总和等于给定总和的索引对

java - 在数组中查找值总和等于给定总和的索引对

问题描述

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

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

蛮力方法是有两个循环，这将花费 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>>. 这里，key 是数组的元素，value 是它们各自的索引。由于允许重复，因此对于给定的元素可以有多个索引位置。所以地图中的价值是一个列表。

标签： javacarraysalgorithmdata-structures

解决方案

你的方法是绝对正确的。

使用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));        
    }
}

请随时提出疑问。

推荐阅读