Python中小于K的二数之和

假设我们有一个整数数组A和另一个给定的整数K。我们需要找到最大的S，使得存在i < j且A[i] + A[j] = S，并且S < K。如果不存在满足此等式的i、j，则返回-1。例如，如果A = [34,23,1,24,75,33,54,8]且K = 60，则输出将为58，因为我们可以使用34和24相加得到58，小于60。

为了解决这个问题，我们将遵循以下步骤：

  • res = -1
  • 如果A只有一个元素，则返回-1
  • 对于范围从0到A长度的i
    • 对于范围从i+1到A长度的j
      • temp = A[i] + A[j]
      • 如果temp < K，则res = res和temp中的最大值
  • 返回res

示例(Python)

让我们看下面的实现来更好地理解：

 在线演示

class Solution(object):
   def twoSumLessThanK(self, A, K):
      ans = -1
      if len(A)==1:
         return -1
      for i in range(len(A)):
         for j in range(i+1,len(A)):
            temp = A[i]+ A[j]
            if temp<K:
               ans = max(ans,temp)
      return ans
ob1 = Solution()
print(ob1.twoSumLessThanK([34,23,1,24,75,33,54,8],60))

输入

[34,23,1,24,75,33,54,8]
60

输出

58

更新于：2020年4月28日

772 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告