https://www.acmicpc.net/problem/1253
initial
for i in range(2, n):
left, right = 0, 1
tmp = lst[left] + lst[right]
while right < i:
if tmp == lst[i]:
ans += 1
break
elif tmp < lst[i]:
right += 1
tmp += lst[right]
elif right == i:
while left < i:
tmp -= lst[left]
left += 1
else:
tmp -= lst[left]
left += 1
print(ans)
My initial idea was to make left and right pointer all to the left of the current number index.
But once you realise that your implementation is unnecessarily complex, thats when you know you need backtrack a lot (not just a bit but a lot) and think of another way.
When 2 sum is equal to the target, we need to check if this is a valid case i.e. the left and right pointers are not at the current number index i. If they are, we increment and decrement the left and right pointers respectively.
Another approach would be to redeclare the given lst to exclude the current number index by slicing (but you have to save that number in a separate variable beforehand). Then we dont have to check for valid cases when sum of left and right pointer equals to that target number.
solution
n = int(input())
lst = list(map(int, input().split()))
lst.sort()
ans = 0
for i in range(n):
left, right = 0, n-1
while left < right:
tmp = lst[left] + lst[right]
if tmp == lst[i]:
if left == i:
left += 1
elif right == i:
right -= 1
else:
ans += 1
break
elif tmp > lst[i]:
right -= 1
else:
left += 1
print(ans)via slicing
N = int(input())
num2 = list(map(int, input().split()))
num2.sort()
sum_v = 0
for i in range(N):
target = num2[i]
num = num2[:i] + num2[i+1:]
left, right = 0, len(num)-1
while left < right:
if num[left] + num[right] > target:
right -= 1
elif num[left] + num[right] < target:
left += 1
elif num[left] + num[right] == target:
sum_v += 1
break
print(sum_v)
complexity
n log n (cuz sort) + n^2 cuz double for loop
