我怎样才能让这个code，以找到一对有一笔更有效率？更有、效率、code
我在做这测试在testdome.com的乐趣，和它的失败的效率测试。有什么更好的办法是吗？我不指望任何值的两倍。看来要做到这一点的唯一方法是蛮力，这是一个n ^ 2算法。
下面是这个问题的方向：
收件，给定一个列表与目标之和的函数，返回 基于零的任何两个不同的元件，其总和指数等于 目标总和。如果没有这样的元件，该函数应 返回null。
例如，findTwoSum（新INT [] {1，3，5，7，9}，12）应该返回 任何指标以下元组： 1，4（3 + 9 = 12）， 2，3（5 + 7 = 12）， 3，2（7 + 5 = 12）或 4，1（9 + 3 = 12）。
这是我的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:
Write a function that, given a list and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum. If there are no such elements, the function should return null.
For example, findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12) should return any of the following tuples of indices: 1, 4 (3 + 9 = 12), 2, 3 (5 + 7 = 12), 3, 2 (7 + 5 = 12) or 4, 1 (9 + 3 = 12).
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).
