当前位置：文江博客话题详情

在排序数组中查找总和为 K 的一对整数

发布于 2024-11-24 05:00:37 字数 127 浏览 3 评论 0原文

给定一个已排序的整数数组，我们如何找到一对总和为 K 的整数？

例如array = 1,3,5,6,10，K = 6，答案是1和5。

时间复杂度应该最小化。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不必在意 2024-12-01 05:00:37

您可能想查看此博客文章：

http://www.codingatwork.com/ 2011/07/array-sum/

我的方法是对列表进行二分搜索来查找 K/2，然后向左走一个变量 a 并另一个变量 b 正在尝试找到解决方案a+b=K。

这个想法是从小于或等于K/2的最大数字开始a并从大于b的最小数字开始。代码>a。再次使用二分查找查找 a 并将 b 设为数组中的下一个元素。然后

如果a+b = K，则返回(a,b)。
如果 a+b K，然后将b向右移动一位。
如果a+b> K，然后将a向左移动一位。

当然，您可以跳过二分查找，只在数组开头开始 a，在数组末尾开始 b，然后执行

If a +b = K，然后返回(a,b)。
如果 a+b K，然后将a向右移动一位。
如果a+b> K，然后将b向左移动一位。

这可能更快。

回复收藏 0 原文

不顾 2024-12-01 05:00:37

存在线性 (O(n)) 解。

获取一个哈希表，并在遍历数组时检查当前元素是否已在哈希表中 - 如果是，那么您就找到了答案。否则插入等于 K 减去当前元素的数字。顺便说一句，适用于非排序数组。

int[] ar = new int[] { 1, 4, 3, 5 };
int K = 6;

HashSet<int> set = new HashSet<int>();
foreach (int a in ar)
{
    if (set.Contains(a))
    {
        Console.WriteLine(a + ", " + (K - a));
        break;
    }

    set.Add(K - a);
}

There is a linear (O(n)) solution.

Take a hashtable and while iterating through the array check if the current element is already in the hashtable - if so then you've found the answer. Otherwise insert the number which is equal to K minus the current element. Works for non sorted array, btw.

int[] ar = new int[] { 1, 4, 3, 5 };
int K = 6;

HashSet<int> set = new HashSet<int>();
foreach (int a in ar)
{
    if (set.Contains(a))
    {
        Console.WriteLine(a + ", " + (K - a));
        break;
    }

    set.Add(K - a);
}

回复收藏 0 原文

灯下孤影 2024-12-01 05:00:37

function findpairzero(arr) {
 let left = 0;
 let right = arr.length - 1;

 while (left < right) {
 if (arr[left] + arr[right] === 0) {
  return [arr[left], arr[right]];
  } else if (arr[left] + arr[right] > 0) {
  right--;
  } else {
  left++;
 }
}
}

console.log(findpairzero([-4, -3, -2, -1, 0, 3, 2, 4, 5]));

function findpairzero(arr) {
 let left = 0;
 let right = arr.length - 1;

 while (left < right) {
 if (arr[left] + arr[right] === 0) {
  return [arr[left], arr[right]];
  } else if (arr[left] + arr[right] > 0) {
  right--;
  } else {
  left++;
 }
}
}

console.log(findpairzero([-4, -3, -2, -1, 0, 3, 2, 4, 5]));

回复收藏 0 原文

~没有更多了~