我在testdome.com上做这个有趣的测试(点击此处可查看),但未能通过效率测试。你有更好的方法吗?我没有重复计算任何值。这似乎是唯一的办法就是采用暴力方法,即n^2算法。
以下是该问题的说明:
编写一个函数,给出一个列表和一个目标总和,返回两个不同元素的下标和等于目标总和的结果。如果没有这样的元素,则应返回null。
例如,findTwoSum(new 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)。
下面是我的代码:
根据Kon的建议,一次性完成以下操作:
以下是该问题的说明:
编写一个函数,给出一个列表和一个目标总和,返回两个不同元素的下标和等于目标总和的结果。如果没有这样的元素,则应返回null。
例如,findTwoSum(new 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)。
下面是我的代码:
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]);
}
编辑:这是我的最终可行代码。谢谢大家!
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]);
}
}
根据Kon的建议,一次性完成以下操作:
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;
}
n^2
的时间内给出一个解决方案。但是有可能用线性时间得到一个解决方案。该解决方案使用了一个非常流行的数据结构。你能否想一想并取得进展? - Kon