In this type of sentence where the verb in the main clause is a synonym of "think", "believe", etc., English speakers tend to "promote" the negative to the main clause. So even if what is logically meant is:
"I believe that we haven't met"
"I think you won't have any trouble with this"
"I suppose that you can't leave work early"
people would actually tend to say:
"I don't believe we've met"
"I don't think you'll have any trouble with this"
"I don't suppose you can leave work early"
You could argue that there is in principle a difference in nuance between the two variants. But in practice, this nuance doesn't tend to be exercised, and speakers simply tend to favour the version with the negative in the main clause. Whereas, conversely, other languages may have a preference for putting the negative in the subordinate clause.