Why is my python code so slow (leetcode)?

Question

Given an array of integers, each element appears twice, with the exception of one. Find this one.

Note: Your algorithm must have linear execution complexity. Could you implement it without using additional memory?

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        prev = []
        for i,j in enumerate(nums):
            if j in prev:
                nums[i] = -j
            else:
                prev.append(j)
        return sum(nums)

This is a question from leetcode and actually one that has the highest AC speed. However, as my code goes, it tells me that Time Limit is Exceeded and cannot be accepted. Can anyone analyze my code, including complexity? Thank you so much.

Upadate: Thanks to everyone, and I changed the "prev" from the list to a set that works beautifully!

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        prev = set([])
        for i,j in enumerate(nums):
            if j in prev:
                nums[i] = -j
            else:
                prev.add(j)
        return sum(nums)

However, I'm still looking for solutions that do not require additional memories, as this question describes.

: , , .

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        for i,j in enumerate(nums):
            if j in set(nums[:i+1]):
                nums[i] = -j
        return sum(nums)

, , nums [: + 1], ? , ? set , .

Answer 1

@Peter :

def singleNumber(nums):
    unique = 0
    for num in nums:
        unique ^= num
    return unique

Answer 2

Xor - . Xor 0, , , , res.

x=[1,1,2,3,2,4,4,5,5]
res=x[0]
for i in xrange(1,len(x)):
    res^=x[i]

print res

Answer 3

, XOR-.

from operator import xor

def single_number(nums):
    return reduce(xor, nums)

Python 3.x(, -, Leetcode) reduce functools.

Answer 4

cython ( , , , ):

Create a file singleNumber.pyxwith the following contents:

def singleNumber(list nums, int nn):
cdef int i, ii, np
cdef list prev = []

for i in xrange(nn):
    np = len(prev)
    for ii in xrange(np):
        if nums[i] == prev[ii]:
            nums[i] = - prev[ii]
        else:
            prev.append(nums[i])
return sum(nums)

Create a file setup.pywith the following contents:

from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize('singleNumber.pyx'),
)

Compile it: python setup.py build_ext --inplace

import singleNumber as sn
arr = [i + 1 for i in range(1000)]
%timeit sn.singleNumber(arr,len(arr))

Result: 100000 loops, best of 3: 15.4 µs per loop

Using the function XORgives me:10000 loops, best of 3: 82.1 µs per loop

EDIT:

I get different results if I use solutions XORcompared to the original function!

from operator import xor

def singleNumber_xor(nums):
    return reduce(xor, nums)

arr = [i + 1 for i in range(10000)]
singleNumber_xor(arr)

Gives me: 10000

Original function:

def singleNumber_orig(nums):
    prev = set([])
    for i,j in enumerate(nums):
        if j in prev:
            nums[i] = -j
        else:
            prev.add(j)
    return sum(nums)

singleNumber_orig(arr)

Gives me: 50005000