Solution:
Let $q$ be an integer such that
$$2 q^{2} \leq n < 2(q+1)^{2}$$
Then
$$n - 2 q^{2} < 4q + 2 \leq 4 \sqrt{\frac{n}{2}} + 2 = 2(\sqrt{2n} + 1)$$
Further, let $t$ be an integer such that $t^{2} \leq n - 2 q^{2} < (t+1)^{2}$. We choose $p$ to be either the number $t$ or $t+1$ depending on the location of $n - 2 q^{2}$ with respect to the midpoint of the interval $[t^{2}, (t+1)^{2}]$. More precisely, we set
$$p= \begin{cases} t, & \text{ if } n-2 q^{2}-t^{2} \leq t \\ t+1, & \text{ if } n-2 q^{2}-t^{2} > t \end{cases}$$
Then we have
$$\left|p^{2}+2 q^{2}-n\right| \leq t \leq \sqrt{n-2 q^{2}} \leq \sqrt{2(\sqrt{2 n}+1)}$$
It remains to note that $\sqrt{2(\sqrt{2 n}+1)} \leq \sqrt[4]{9 n}$ for every $n \geq 160$ and that for $n < 160$ the existence of $p$ and $q$ can be checked directly.