我怎样才能让这个code，以找到一对有一笔更有效率？

问题描述

我在做这测试在testdome.com的乐趣，和它的失败的效率测试。有什么更好的办法是吗？我不指望任何值的两倍。看来要做到这一点的唯一方法是蛮力，这是一个n ^ 2算法。

下面是这个问题的方向：

这是我的code：

 公共类TwoSum {
公共静态INT [] findTwoSum（INT []列表中，INT总和）{
    如果（表== NULL || list.length 2）返回NULL;
    的for（int i = 0; I＆LT; list.length  -  1;我++）{//较低索引元素
        对于（INT J = I + 1; J＆LT; list.length; J ++）{//更高的索引元素
            如果（名单[I] +列表[J] ==总和）{
                返回新INT [] {I，J};
            }
        }
    }

    //没有发现
    返回null;
}


公共静态无效的主要（字串[] args）{
    INT []索引= findTwoSum（新INT [] {1，3，5，7，9}，12）;
    的System.out.println（指数为[0] ++指数为[1]）;
}
 

}

编辑：因此，这里是我的最终工作code。谢谢大家！

 进口的java.util.HashMap;
进口的java.util.Map;

公共类TwoSum {
    公共静态INT [] findTwoSum（INT []列表中，INT总和）{
        如果（表== NULL || list.length 2）返回NULL;
        //映射值指标
        地图＆LT;整数，整数GT; indexMap =新的HashMap＆LT;＆GT;（）;
        的for（int i = 0; I＆LT; list.length;我++）{
            indexMap.put（名单[I]，I）;
        }

        的for（int i = 0; I＆LT; list.length;我++）{
            诠释需要=总和 - 列表[I]
            如果（indexMap.get（需要）！= NULL）{
                返回新INT [] {我，indexMap.get（需要）};
            }
        }

        //没有发现
        返回null;
    }

    公共静态无效的主要（字串[] args）{
        INT []索引= findTwoSum（新INT [] {1，3，5，7，9}，12）;
        的System.out.println（指数为[0] ++指数为[1]）;
    }
}
 

根据Kon的建议，在一通：

 公共静态INT [] findTwoSum（INT []列表中，INT总和）{
    如果（表== NULL || list.length 2）返回NULL;
    //映射值指标
    地图＆LT;整数，整数GT; indexMap =新的HashMap＆LT;＆GT;（）;
    的for（int i = 0; I＆LT; list.length;我++）{
        诠释需要=总和 - 列表[I]
        如果（indexMap.get（需要）！= NULL）{
            返回新INT [] {我，indexMap.get（需要）};
        }

        indexMap.put（名单[I]，I）;
    }

    //没有发现
    返回null;
}
 

解决方案

看看你做的内循环，你的检查，如果列表[I] +列表[J] ==总和。

如果你变换公式略有下降，这意味着定列表[i]和总和（这是内环内的两个常量），你实际上是在问有没有一个索引，其中值（和 - 列表[I]）存储，而这就是你的内循环解决了什么。

现在将使用本质上是的indexOf，你可以解决问题的知识（总和 - 列表[I]） - 以线性时间风格的方法，有数据结构，可以在比Ø更好的时间回答这样的问题（N ）。

I'm doing this test on testdome.com for fun, and it's failing the efficiency test. What better way is there? I'm not counting any values twice. It seems the only way to do this is by brute force, which is an n^2 algorithm.

Here are the directions for the problem:

And here's my code:

public class TwoSum {
public static int[] findTwoSum(int[] list, int sum) {
    if (list == null || list.length < 2) return null;
    for (int i = 0; i < list.length - 1; i++) { //lower indexed element
        for (int j = i + 1; j < list.length; j++) { //higher indexed element
            if (list[i] + list[j] == sum) {
                return new int[]{i, j};
            }
        }
    }

    //none found
    return null;
}


public static void main(String[] args) {
    int[] indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12);
    System.out.println(indices[0] + " " + indices[1]);
}

}

EDIT: So here's my final working code. Thanks everyone!

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static int[] findTwoSum(int[] list, int sum) {
        if (list == null || list.length < 2) return null;
        //map values to indexes
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < list.length; i++) {
            indexMap.put(list[i], i);
        }

        for (int i = 0; i < list.length; i++) {
            int needed = sum - list[i];
            if (indexMap.get(needed) != null) {
                return new int[]{i, indexMap.get(needed)};
            }
        }

        //none found
        return null;
    }

    public static void main(String[] args) {
        int[] indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12);
        System.out.println(indices[0] + " " + indices[1]);
    }
}

As per Kon's suggestion, in one pass:

public static int[] findTwoSum(int[] list, int sum) {
    if (list == null || list.length < 2) return null;
    //map values to indexes
    Map<Integer, Integer> indexMap = new HashMap<>();
    for (int i = 0; i < list.length; i++) {
        int needed = sum - list[i];
        if (indexMap.get(needed) != null) {
            return new int[]{i, indexMap.get(needed)};
        }

        indexMap.put(list[i], i);
    }

    //none found
    return null;
}

解决方案

Look at what you do in the inner loop, your checking if list[i] + list[j] == sum.

If you transform the equation slightly, it means given list[i] and sum (which are both constants within the inner loop), you are really asking "is there an index where the value (sum - list[i]) is stored", and thats what your inner loop solves.

Now applying the knowledge that you could solve the problem using essentially a indexOf(sum - list[i])-style method in linear time, there are data structures that can answer this kind of question in better time than O(N).

这篇关于我怎样才能让这个code，以找到一对有一笔更有效率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！