파이썬에서 이 쌍의 합 사이의 차이가 최소화되는 두 쌍의 숫자를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있고 이 두 쌍의 합 사이의 절대 차이가 최소화되도록 두 쌍의 숫자를 선택하려고 한다고 가정합니다.

따라서 입력이 nums =[3, 4, 5, 10, 7]과 같으면 이 쌍(3 + 7) - (4 + 5) =1을 선택할 수 있으므로 출력은 1이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

거리:=새 목록
0에서 숫자 - 2의 크기 범위에 있는 i에 대해
- i + 1 범위에서 nums - 1까지의 j에 대해, do
  - 목록 삽입 [|nums[i] - nums[j]| , i, j] 거리 끝에서
- 목록 거리 정렬
- an :=1^9
- 범위 0에서 거리 크기 - 2의 i에 대해
  - [거리, i1, i2] :=거리[i]
  - j :=나는 + 1
  - [dist2, i3, i4] :=거리[j]
  - j <(i1, i2, i3, i4)의 거리와 요소의 크기가 고유하지 않은 동안 do
    - [dist2, i3, i4] :=거리[j]
    - j :=j + 1
  - (i1, i2, i3, i4)의 요소가 고유한 경우
    - ans :=ans 및 (dist2 - dist)의 최소값
  - 반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시 코드

class Solution:
   def solve(self, nums):
      distances = []
      for i in range(len(nums) - 1):
         for j in range(i + 1, len(nums)):
            distances.append((abs(nums[i] - nums[j]), i, j))
      distances.sort()
      ans = 1e9
      for i in range(len(distances) - 1):
         dist, i1, i2 = distances[i]
         j = i + 1
         dist2, i3, i4 = distances[j]
         while j < len(distances) and len({i1, i2, i3, i4}) != 4:
            dist2, i3, i4 = distances[j]
            j += 1
         if len({i1, i2, i3, i4}) == 4:
            ans = min(ans, dist2 - dist)
      return ans

ob = Solution()
nums = [3, 4, 5, 10, 7]
print(ob.solve(nums))

입력

[3, 4, 5, 10, 7]