// Checks whether the array contains two elements whose sum is s.
// Input: A list of numbers and an integer s
// Output: return True if the answer is yes, else return False
public static boolean calvalue (int[] numbers, int s){
for (int i=0; i< numbers.length; i++){
for (int j=i+1; j<numbers.length;j++){
if (numbers[i] < s){
if (numbers[i]+numbers[j] == s){
return true;
}
}
}
}
return false;
}
问问题
24416 次
5 回答
16
这可以在 O(n) 中实现。
- 从您的列表中创建一个以哈希为基础的集合，使其包含列表的所有元素。这需要 O(n)。
- 遍历
n列表中的每个元素，计算s-n = d并检查d集合中是否存在 。如果d存在，则n+d = s，所以返回true。如果您通过列表但没有找到合适的d，请返回false。这是通过您的列表单次完成的，每次查找需要 O(1)，所以这一步也需要 O(n)。
于 2012-10-08T03:32:09.120 回答
7
本文其他答案中提到的解决方案以及其他一些答案（例如，使用位图而不是哈希表）都出现在问题的以下重复项和细微变化中：
•在数组中查找两个元素与 k 的和，
•从数组中找到一对元素，其和等于给定数字，
• 确定集合 s 中是否存在两个元素的和恰好等于，
• 检查 2 个数组的数字加起来是否为 i，
•在数组中找到与给定总和相加的数字对，
• 设计一种算法来查找数组中所有整数对，其总和为 a，
• 给定一个未排序数组，找出数组中任意两个总和等于 t 的元素，
•一种递归算法，用于在数组中找到两个整数，总和为给定整数，
•在未排序数组中找到等于给定总和的 2 个数字，
•找到两个元素，使总和等于给定值，
• 并且，根据谷歌，还有更多。
于 2012-10-08T05:31:01.960 回答
5
您可以通过对数组进行排序来解决此问题，然后保留 2 个指向数组开头和结尾的指针，并通过移动两个指针来找到 2 个数字。排序步骤需要 O(nlog n)，第二步需要 O(n)。
正如@Adam 所指出的，从数组中删除重复元素也很好，这样如果数组包含许多重复数字，您可以减少第二步的时间。
至于第二步怎么做：
- 如果当前 2 个数字的总和大于 n，则将末尾的指针向后移动。
- 如果当前 2 个数字之和小于 n，则将开始处的指针向前移动。
- 当两个指针指向同一个元素时停止并拒绝。如果 sum 等于 n，则接受。
为什么这是正确的（我用右端表示大端，左端表示小端）：
- 如果 sum 大于 n，则使用右端没有意义，因为所有大于当前左端的数字都会使其变得更糟。
- 如果 sum 小于 n，则使用左端没有意义，因为所有小于当前右端的数字都会使其变得更糟。
- 在每个步骤中，我们将遍历已删除数字和剩余数字之间的所有可能组合（逻辑上）。最后，我们将穷尽所有数字对之间所有可能的组合。
于 2012-10-08T03:26:24.253 回答
1
这是一个考虑到重复条目的解决方案。它是用 javascript 编写的，并假定数组已排序。
var count_pairs = function(_arr,x) {
if(!x) x = 0;
var pairs = 0;
var i = 0;
var k = _arr.length-1;
if((k+1)<2) return pairs;
var halfX = x/2;
while(i<k) {
var curK = _arr[k];
var curI = _arr[i];
var pairsThisLoop = 0;
if(curK+curI==x) {
// if midpoint and equal find combinations
if(curK==curI) {
var comb = 1;
while(--k>=i) pairs+=(comb++);
break;
}
// count pair and k duplicates
pairsThisLoop++;
while(_arr[--k]==curK) pairsThisLoop++;
// add k side pairs to running total for every i side pair found
pairs+=pairsThisLoop;
while(_arr[++i]==curI) pairs+=pairsThisLoop;
} else {
// if we are at a mid point
if(curK==curI) break;
var distK = Math.abs(halfX-curK);
var distI = Math.abs(halfX-curI);
if(distI > distK) while(_arr[++i]==curI);
else while(_arr[--k]==curK);
}
}
return pairs;
}
享受！
于 2013-03-29T14:20:34.743 回答
0
在 Java 中
private static boolean find(int[] nums, long k, int[] ids) {
// walk from both sides towards center.
// index[0] keep left side index, index[1] keep right side index,
// runtime O(N)
int l = ids[0];
int r = ids[1];
if (l == r) {
ids[0] = -1;
ids[1] = -1;
return false;
}
if (nums[l] + nums[r] == k) {
ids[0]++;
ids[1]++;
return true;
}
if (nums[l] + nums[r] < k) {
ids[0]++;
} else {
ids[1]--;
}
return find(nums, k, ids);
}
public static boolean twoSum(final int[] nums, int target) {
// Arrays.sort(nums); //if the nums is not sorted, then sorted it firstly, thus the running time will be O(NlogN)
int[] ids = new int[2];
ids[0] = 0;
ids[1] = nums.length - 1;
return find(nums, target, ids);
}
测试
@Test(timeout = 10L, expected = Test.None.class)
public void test() {
Assert.assertEquals( twoSum(new int[]{3, 2, 4}, 6), true);
Assert.assertEquals( twoSum(new int[]{3, 2, 4}, 8), false);
}
IF只回答是不够的，想知道A[i]+A[j]=target的i和j是哪一个
@cheeken 的思路如下，如果有重复号码，取第一个出现的。
public static int[] twoSum2(final int[] nums, int target) {
int[] r = new int[2];
r[0] = -1;
r[1] = -1;
Set<Integer> set = new HashSet<>(nums.length);
Map<Integer, List<Integer>> map = new HashMap<>(nums.length);
for (int i = 0; i < nums.length; i++) {
int v = nums[i];
if (set.contains(target - v)) {
r[0] = map.get(target - v).get(0);
r[1] = i;
return r;
}
set.add(v);
List ids = map.get(v);
if (ids == null) {
ids = new LinkedList<>();
ids.add(i);
map.put(v, ids);
} else {
ids.add(i);
map.put(v, ids);
}
}
return r;
}
测试
int[] r = twoSum2(new int[]{3, 2, 4}, 6);
Assert.assertEquals(r[0], 1);
Assert.assertEquals(r[1], 2);
r = twoSum2(new int[]{3, 2, 4}, 8);
Assert.assertEquals(r[0], r[1]);
Assert.assertEquals(r[1], -1);
于 2016-02-05T21:03:52.903 回答