小于K的两数之和

给你一个整数数组 A 和一个整数 K,请在该数组中找出两个元素,使它们的和小于 K但尽可能地接近 K返回这两个元素的和

如不存在这样的两个元素,请返回 -1

示例1:

输入:A = [34,23,1,24,75,33,54,8], K = 60
输出:58
解释:
34 和 24 相加得到 58,58 小于 60,满足题意。

示例2:

输入:A = [10,20,30], K = 15
输出:-1
解释:无法找到和小于 15 的两个元素

思路:

首先对数组进行排序。然后左指针指向第一个元素,右指针指向第二个元素。将左指针和右指针对应的值相加,如果>=K,则右指针移动一位。如果小于K,则左指针移动一位。

例子:

数组:K=60

1,8,33,54,23,34,24,75

排序后:

1 8 23 24 33 34 54 75

L                              R

1+75>K,R移动一位

1 8 23 24 33 34 54 75

L                         R 

 

1+54 < K,L移动一位,此时记录sum=55

1 8 23 24 33 34 54 75

   L                      R

8+54 > K, R移动一位

1 8 23 24 33 34 54 75

   L                 R

8+34 < K,L移动一位

1 8 23 24 33 34 54 75

      L              R

23+34 < K,L移动一位。此时的值为57>sum,因此sum更新为57

1 8 23 24 33 34 54 75

            L        R

24+34 < K, L移动一位,此时值为58大于sum,sum更新为58

 1 8 23 24 33 34 54 75

                  L   R

33+34 > K,R 移动一位,此时L=R,退出循环。最终得到的sum值为58

对应代码如下:

void insert_sort(int arrary[],int len)
{
	int i, j;
	int temp;
	for (i = 1; i < len; i++)
	{
		j = i;
		while (j > 0 && arrary[j] < arrary[j - 1])
		{
			temp = arrary[j];
			arrary[j] = arrary[j - 1];
			arrary[j - 1] = temp;
			j--;
		}
	}
}
int TwoSumLessThanK(int a[], int len,int k)
{
	int left, right,sum;
	left = 0;
	right = len-1;
	insert_sort(a, len);
	//初始化sum等于排序后的第一个值,也就是最小的值
	sum = a[left];
	while (left < right)
	{
		if (a[left] + a[right] < k)
		{
			sum = a[left] + a[right] > sum ? a[left] + a[right] : sum;
			left += 1;
		}
		else
		{
			right -= 1;
		}
	}
	//如果sum值一直等于初始值,证明不存在这样的两个元素,则返回-1
	return sum == a[left]?-1:sum;
}

  

原文地址:https://www.cnblogs.com/zhanghongfeng/p/11646203.html