18156: 寻找离目标数最近的两数之和

two pointers , http://cs101.openjudge.cn/practice/18156

给定一组数S（可能包含相同的数），从中选取两个数，使两数之和离目标数T最近。

输入

输入包含两行。第一行为目标数T。第二行为S中的N个数字，每个数之间以空格隔开。注意： 2 <= N <= 100000

输出

输出离T最近的两数之和。如果存在多个解，则输出数值较小的那个。

样例输入

14
3 7 8 3 9

样例输出

来源：cs101-2017 期末机考备选

移动指针前更新答案，不会跳过某些潜在的最优解。

python

def closest_sum_to_target(T, S):
    S.sort()
    left, right = 0, len(S) - 1
    closest_sum = float('inf')
    min_diff = float('inf')

    while left < right:
        current_sum = S[left] + S[right]
        diff = abs(current_sum - T)

        if diff < min_diff or (diff == min_diff and current_sum < closest_sum):
            closest_sum = current_sum
            min_diff = diff

        if current_sum < T:
            left += 1
        else:
            right -= 1

    return closest_sum

# 输入处理部分
T = int(input())
S = list(map(int, input().split()))
print(closest_sum_to_target(T, S))

2020fall-cs101，王康安.

思路：先排序，一个头指针，一个尾指针，求和。如果和大于T ，尾指针左移；如果小，头指针右移。

python

tar = int(input())  #target
s = [int(x) for x in input().split()]
s.sort()

ans = 200000
gap = 100000 - 2

h = 0               #head
t = len(s) - 1      #tail
while h < t:
    mid = s[h] + s[t]
    if mid == tar:
        ans = mid
        break
    
    if abs(mid - tar) < gap:
        gap = abs(mid - tar)
        ans = mid
    if abs(mid - tar) == gap:
        ans = min(ans, mid)
        
    if mid > tar:
        t -= 1
    elif mid < tar:
        h += 1
    
print(ans)

18156: 寻找离目标数最近的两数之和 ​

18156: 寻找离目标数最近的两数之和