Two Sum Less Than K ใน Python

สมมติว่าเรามีอาร์เรย์ 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
for i ในช่วง 0 ถึงความยาวของ A
- for j ในช่วง i + 1 ถึงความยาวของ A
  - temp = A[i] + A[j]
  - ถ้า temp < K แล้ว res = max ของ 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